QuestBench: Can LLMs ask the right question to acquire information in reasoning tasks?

🎯 Pitch

LLMs ace multi-step reasoning when all facts are given, but on QuestBench they falter—scoring only 40–50% on logic and planning when they must detect a single missing variable and choose the one question that unlocks the solution. Strikingly, even models that easily solve the full version of a problem fail to ask for the needed clue, revealing that strong reasoning does not imply knowing what you do not know.

1. Executive Summary

This paper introduces QuestBench, a benchmark for evaluating whether LLMs can identify the minimal necessary question to ask when a reasoning task is underspecified, formalizing the information-gathering problem as a constraint satisfaction problem (CSP) with missing variable assignments. The benchmark spans four domains—Logic-Q (logical reasoning with one missing proposition), Planning-Q (PDDL planning problems with partially observed initial states), GSM-Q (human-annotated grade school math problems missing one variable), and GSME-Q (equation-based versions of GSM-Q)—and requires models to select the correct clarification question from multiple choices rather than solve the underlying task. While current state-of-the-art models achieve over 80% accuracy on the math domains, they reach only 40-50% on Logic-Q and Planning-Q, and critically, models struggle to identify the right question even when they can solve the fully specified version of the same problem, establishing that the ability to reason with sufficient information is not sufficient for effective information acquisition.

2. Context and Motivation

The Core Problem: LLMs Cannot Identify What Information They're Missing

The fundamental question this paper tackles is straightforward but underexplored: can LLMs recognize when they lack enough information to solve a reasoning task, and can they determine exactly what question to ask to acquire that missing information?

This matters because the prevailing paradigm for deploying LLMs on reasoning tasks assumes well-specified problems — the user provides all necessary information upfront, and the model's job is to reason over what it's been given. Benchmarks like GSM8k (Cobbe et al., 2021), MATH (Hendrycks et al., 2021), and various logical reasoning datasets (Zhang et al., 2023; Chen et al., 2024b) are built on this assumption. But as the paper points out in Section 1, real-world scenarios frequently violate it:

"Users may omit crucial details in math problems, and robots might operate in environments with partial observability."

The gap is significant for several practical reasons the paper discusses explicitly and implicitly throughout Sections 1-3:

Interactive AI assistants: If a user asks "how many eggs does Janet have now" without specifying how many she started with, a useful assistant should ask for the missing information rather than hallucinating a number or responding with an unsolvable error message. This capability is central to building trustworthy systems, particularly in high-stakes domains like education, healthcare, and scientific research where the authors note (Appendix H) that "clarifying underspecified inputs can reduce misunderstandings and improve decision-making."
Autonomous systems under partial observability: Robots and planning agents routinely operate in environments where the full state is unknown. The Planning-Q domain (Section 4.2) formalizes this: given a partially observed initial state of a Blocks World configuration, what is the single most informative observation to make? An agent that can identify minimal necessary queries can operate more efficiently than one that probes randomly or exhaustively.
Epistemic humility and safety: The paper connects information-gathering ability to model uncertainty (Sections 5.4 and 5.3, with further discussion in Appendix H). A model that can detect when it doesn't know enough and ask for clarification is fundamentally more aligned — it avoids overconfident incorrect answers — than one that attempts to solve underspecified problems regardless. This is what the authors frame as "epistemic humility" (Appendix H).
Formalizing underspecification vs. ambiguity: The paper draws a critical distinction in Section 3.1 that prior work largely conflated. Semantic ambiguity means the natural language query admits multiple valid interpretations, each potentially yielding a different well-specified CSP — for example, "10% of that" where "that" has an unclear antecedent. Underspecification means the CSP itself is missing variable assignments or constraints at Stage 2 (the solving stage), regardless of whether the natural language was parsed unambiguously at Stage 1. This distinction is more than taxonomic: it means prior work on ambiguity (see below) largely addressed a different problem from the one QuestBench targets, and existing ambiguity-handling techniques are consequently insufficient.

Conflicting or Incomplete Prior Evidence

The field of LLM question-asking is not new, but the paper argues it has been studied in settings that are difficult to evaluate objectively, or that address a fundamentally different type of missing information. The paper identifies several bodies of prior work and explains why each falls short for the specific problem QuestBench targets.

Subjective and ambiguous tasks dominate existing question-asking benchmarks. Most prior work on LLMs asking clarifying questions focuses on domains where there is no single ground-truth "right" question (Section 2). Task-oriented dialogue benchmarks like MultiWOZ (Budzianowski et al., 2018) and SGD (Rastogi et al., 2020) involve ambiguous user intents where multiple clarifying questions could be valid, depending on context. Preference elicitation work (Li et al., 2023; Handa et al., 2024) asks models to infer subjective user preferences, where the "correct" question depends on the user's internal state. Visual question-answering benchmarks like Chandu et al. (2024) target epistemic and aleatoric uncertainty but conflate the two types. As the paper notes in Section 2:

"This makes objective evaluation of information-gathering abilities difficult in these settings."

Without a ground-truth answer for what constitutes the correct clarifying question — and in subjective domains there fundamentally isn't one — it's impossible to measure whether a model is actually good at identifying missing information or merely producing plausible-sounding questions.

Semantic ambiguity is well-studied, but underspecification is not. Prior work extensively addresses semantic ambiguity — the problem of a natural language query having multiple valid interpretations. Kuhn et al. (2023b) formalizes semantic uncertainty for natural language generation. Zhang et al. (2024a) provides a taxonomy of ambiguity types. Min et al. (2020) handles ambiguous open-domain questions. But all of this work operates at Stage 1 of the paper's two-stage formulation (Section 3.1): parsing natural language into a CSP. Once parsing is done (or for tasks like Logic-Q and Planning-Q where inputs are already symbolic), the underspecification problem — missing variable assignments in an otherwise well-defined CSP — is a separate challenge that prior work has not systematically studied.

Question-asking methods exist but target the wrong problems. Several methods have been proposed to enhance LLMs' question-asking abilities. Andukuri et al. (2024) uses STaR-GATE to teach models to ask clarifying questions, but focuses on subjective recipe recommendation. Pang et al. (2024) and Zhang and Choi (2023) address knowledge-based questions (e.g., "who won the sports event?") where the model needs to query for factual information it lacks. Approaches like Grand et al. (2024) and Handa et al. (2024) compute information gain to select informative questions, but their evaluation domains (Battleship, preference elicitation) involve uncertainty about hidden states rather than missing constraints in a reasoning structure.

Zhang and Choi (2023) decomposes question-asking into three stages: detecting when clarification is needed, identifying the appropriate question, and responding based on new information. This decomposition is relevant to QuestBench's structure, but the paper argues (Section 2) that prior instantiations of this pipeline "primarily focus on subjective tasks or require substantial user simulation," making it impossible to evaluate Stage 2 (identifying the right question) in isolation with a ground-truth correctness signal.

General reasoning benchmarks ignore information acquisition entirely. The paper situates itself against the dominant paradigm in LLM reasoning evaluation. Benchmarks like GSM8k, MATH, SimpleLogic (Zhang et al., 2023), and Blocks World planning (via PyperPlan, Alkhazraji et al., 2020) all provide well-specified problems where all necessary information is present. Models are evaluated on whether they can solve the problem given complete information, not on whether they can detect when information is missing. QuestBench is explicitly constructed on top of these existing reasoning benchmarks — Logic-Q extends SimpleLogic, GSM-Q and GSME-Q extend GSM-Plus (Li et al., 2024a), Planning-Q extends PyperPlan — but transforms them into underspecified variants where the original reasoning ability is necessary but not sufficient.

Where Existing Approaches Fall Short

The paper identifies specific limitations that justify a new benchmark rather than repurposing existing resources:

No ground-truth standard for question correctness in prior work. The authors explicitly distinguish their approach in Section 2:

"In contrast, our work focuses on reasoning tasks with a clearly defined ground truth. For each task, the model needs to ask exactly one question, allowing for reliable evaluation of LLMs' information-gathering capabilities."

This is the central methodological contribution of QuestBench: by formalizing underspecification as a 1-sufficient CSP (Definition 3.3), the paper creates problems where the set of correct clarifying questions is mathematically determined — a variable is sufficient if and only if knowing its value, combined with existing assignments and constraints, uniquely determines the target variable. There is no subjectivity about whether a question is "good" or not; it either satisfies the formal sufficiency condition or it doesn't. This enables the kind of rigorous quantitative evaluation that prior question-asking benchmarks could not provide.

Reasoning ability does not imply question-asking ability. Perhaps the most important empirical finding that motivates the benchmark's existence is the ablation study in Section 5.3, which the executive summary references and which we'll detail further in later sections. The paper demonstrates that even when a model can solve the fully-specified version of a QuestBench problem (i.e., when it has all necessary information), its accuracy at identifying the missing question does not approach 100% — particularly in Logic-Q and Planning-Q (Table 5). This means that the capability gap QuestBench measures is not simply a function of the underlying reasoning difficulty. The model fails at the meta-cognitive task of determining what information it needs, even when it possesses the reasoning skills to use that information once acquired.

The distinction between 1-sufficient and k-sufficient problems is a necessary simplification, not a limitation. The paper acknowledges that real-world problems may require multiple clarifying questions (𝑘-sufficient CSPs), and explicitly defines 1-sufficient CSPs as a "fundamental building block" (Section 3.3). The rationale for this design choice is both methodological and practical:

Evaluability: 𝑘-sufficient problems require evaluating sequences of questions where each subsequent question depends on the answer to the previous one. This creates a combinatorial explosion in evaluation complexity and requires simulating user responses, which the paper identifies as a major bottleneck (Section 6, Appendix H). 1-sufficient problems can be cleanly cast as multiple-choice.
Upper bound interpretation: Performance on 1-sufficient CSPs provides "an approximate upper bound on a model's capacity for information acquisition, since any 𝑘-sufficient CSP can become 1-sufficient after 𝑘−1 clarifying questions" (Section 3.3). If a model cannot handle the 1-sufficient case, it will necessarily fail on harder 𝑘-sufficient problems.
Difficulty diversity within the 1-sufficient setting: The paper demonstrates (Section 3.4, Table 1, Figure 4) that 1-sufficient CSPs span a wide range of difficulty as measured by search depth, number of variables, number of constraints, and expected brute-force guesses. So the simplification to 1-sufficient does not make the benchmark trivially easy — the hardest Logic-Q and Planning-Q problems involve dozens of variables, constraints, and search depths up to 14, which even the best models cannot handle (Table 2).

How This Paper Positions Itself

The paper frames itself not as proposing a new method for question-asking, but as creating the evaluation infrastructure and formal framework that makes rigorous study of question-asking possible. Its contributions (stated in Section 1) are:

A formal problem formulation (Section 3) that uses constraint satisfaction to define underspecification in a way that is objective, evaluable, and distinct from semantic ambiguity. This formulation is domain-agnostic — it applies to logic, planning, and math — and provides a common language for studying information acquisition across reasoning tasks.
A benchmark (QuestBench) that instantiates this formulation across four domains, each tapping different reasoning skills: propositional logic deduction (Logic-Q), sequential planning under partial observability (Planning-Q), and algebraic variable substitution in both symbolic (GSME-Q) and natural language (GSM-Q) forms. The benchmark uses a multiple-choice format to enable automated, reproducible evaluation with ground-truth correctness.
Empirical analysis of state-of-the-art LLMs that reveals sharp domain-dependent performance cliffs (Table 2: over 80% on math, under 50% on logic and planning), investigates what problem properties correlate with difficulty (Table 3, Figure 4), and demonstrates through ablation that question-asking is a distinct capability from reasoning (Section 5.3, Table 5).

The paper positions QuestBench as a necessary precursor to developing better question-asking methods (Section 6):

"We believe the multiple-choice format for evaluating question-asking is a necessary precursor to open-ended formats for question asking, since it is valuable for automated and rigorous evaluation. However, once a new approach makes open-ended evaluation viable and reliable, our benchmark can be readily used by simply omitting the multiple-choice options."

This reveals a deliberate research strategy: first establish rigorous evaluation with ground-truth answers in the simplified multiple-choice setting, then use that infrastructure to validate methods that could generalize to open-ended question generation. The benchmark is designed to be forward-compatible — the underlying CSPs remain valid evaluation targets regardless of the output format.

Finally, the paper explicitly connects to broader discussions about model uncertainty and safety. By creating tasks where models must recognize their own knowledge gaps and identify what they need to know, QuestBench provides a well-defined testbed for studying epistemic humility — a capability the authors argue (Appendix H) is "increasingly important for alignment and safety." The finding in Section 5.4 that models perform near-randomly at detecting underspecification in Planning-Q (Table 7) underscores that current LLMs lack this humility in systematic ways, even as they appear confident and capable on well-specified benchmarks.

3. Technical Approach

3.1 Reader Orientation

This is primarily a benchmark construction and evaluation paper whose core idea is that the problem of asking clarifying questions for reasoning tasks can be formalized as identifying which variable in an underspecified constraint satisfaction problem needs to be assigned to make the target variable computable. Rather than proposing a new model or training method, the paper builds a systematic framework for converting existing reasoning datasets into 1-sufficient CSPs — problems where exactly one variable's value is missing but necessary — and then evaluates whether LLMs can correctly identify that variable from a set of multiple-choice options. The system being built is the benchmark itself: a pipeline that takes well-specified reasoning problems, algorithmically removes information to create underspecified variants, mathematically verifies that exactly one clarifying question is both necessary and sufficient, and presents these as evaluation tasks with ground-truth correct answers defined by the CSP structure rather than human judgment.

3.2 Big-Picture Architecture (Diagram in Words)

The QuestBench construction pipeline has five major stages that transform existing well-specified reasoning datasets into 1-sufficient CSP evaluation tasks:

Task formalization (Section 3.2): Each original reasoning problem is converted into a CSP tuple ⟨𝑋, 𝐷, 𝐶, 𝐴, 𝑦⟩ — a set of variables, their domains, constraints relating them, known variable assignments, and a target variable to solve for. This conversion is domain-specific (Logic-Q uses propositional logic atoms, Planning-Q uses PDDL state atoms, GSM-Q/GSME-Q uses math equation variables) but the CSP representation is universal.
Well-specified CSP solution space enumeration (Sections B.1.1, B.2.1): For each domain, backwards search is used to enumerate all partial variable assignments that would uniquely determine the target variable's value. In Logic-Q, this means finding all combinations of property assignments that imply the target is true or false. In Planning-Q, this means finding all partial initial states from which a unique optimal action sequence reaches the goal.
1-sufficient CSP construction (Sections B.1.2, B.2.2): From the well-specified partial states, a single variable assignment is removed to create an underspecified CSP. The resulting partial assignment is verified mathematically to ensure that exactly one additional variable's value is needed to determine the target, and that no other single variable would also work (or if multiple work, any of them is treated as correct). This verification uses the formal definitions of sufficiency (Definition 3.2) and 1-sufficiency (Definition 3.3).
Multiple-choice question generation (Section 4): For each 1-sufficient CSP, the set of variable choices is constructed — typically all variables in the problem plus a "No questions needed" option. The correct choices are those variables whose values, if known, would make the target variable computable (i.e., the elements of the sufficient set). The model must select from these options.
Evaluation and analysis (Section 5): LLMs are prompted with the underspecified problem formulation (natural language for GSM-Q, symbolic PDDL for Planning-Q, rules-and-facts for Logic-Q) and the list of possible questions. The model's selection is compared against the ground-truth sufficient variable set. Additional analyses correlate accuracy with problem complexity metrics (search depth, variable count, constraint count, expected brute-force guesses).

3.3 Roadmap for the Deep Dive

First, the CSP formalization (Section 3.2), including Definitions 3.1-3.3, because the entire benchmark's construction and evaluation depends on the mathematical definitions of Known, underspecification, sufficient sets, and 1-sufficiency. Understanding these definitions is prerequisite to understanding how problems are algorithmically generated.
Second, the difficulty axes (Section 3.4), because these formalize why some 1-sufficient CSPs are harder than others and provide the quantitative framework for the correlation analyses in Section 5.2. The axes connect the CSP structure to search algorithm complexity, making the empirical difficulty trends interpretable.
Third, the domain-specific CSP construction procedures (Logic-Q, Planning-Q, GSM-Q/GSME-Q), which show how the abstract CSP framework is instantiated differently for propositional logic, PDDL planning, and algebraic math problems. Each domain requires its own algorithm for backwards search and 1-sufficiency verification, and the differences explain why models perform differently across domains.
Fourth, the evaluation protocol — the prompt formats, multiple-choice structure, correctness criteria, and cross-validation methodology used to ensure that the benchmark measures what it claims to measure. This covers both the primary question-asking evaluation (Section 5.1) and the ablation studies on well-specified reasoning (Section 5.3) and underspecification detection (Section 5.4).

3.4 Detailed, Sentence-Based Technical Breakdown

This is a benchmark design and empirical analysis paper whose core contribution is a formal framework for evaluating information acquisition in reasoning tasks. The approach has two layers: a mathematical layer (the CSP formalization that defines correctness) and an algorithmic layer (the domain-specific procedures that construct valid benchmark instances). We begin with the mathematical layer because it's shared across all domains.

The CSP Formalization of Underspecification

The paper models every reasoning task as a constraint satisfaction problem (CSP) — a structured representation where the goal is to find the value of a target variable given constraints relating variables to each other and known assignments of some variables to values.

The CSP tuple. Formally, a CSP is a 5-tuple:

$\langle X, D, C, A, y \rangle$

where $X = \{x_i\}_{i=1}^N$ is the set of $N$ variables; $D = \{D_i\}_{i=1}^N$ is the set of domains, with $D_i$ being the possible values $x_i$ can take; $C = \{c_j\}_{j=1}^M$ is the set of $M$ constraints, where each $c_j$ is a boolean function taking a subset of variables as input and returning True or False; $A = \bigwedge_{i \in I_A} (x_i = v_i)$ is a conjunction of known variable assignments, each a pair $(x_i, v_i)$ with $v_i \in D_i$ ; and $y$ is the target variable — the answer the user wants to compute.

What this represents operationally: a reasoning problem is defined by a collection of variables with known or unknown values, rules that constrain how values relate to each other, and a specific variable whose value the system must determine. The system can use the constraints $C$ and the known assignments $A$ to derive unknown variable values through logical deduction or algebraic substitution. The CSP abstraction captures this deductive structure independently of the problem's surface form (natural language, PDDL, or equations).

Why this form: the CSP representation separates what the model knows ( $A$ ) from what it can figure out (through $C$ ) and what it needs to compute ( $y$ ). This allows a formal, computable definition of underspecification that doesn't depend on natural language interpretation or human judgment. Alternative representations like raw text or task-specific structures would make it impossible to mathematically verify that a problem is underspecified or that a particular question resolves the underspecification.

The Known predicate. The paper introduces a convenience predicate used throughout the formal definitions. Known(x) is true when the value of variable $x$ is determinable — either because it's directly assigned in $A$ (so $A \implies \text{Known}(x_i)$ for all $x_i$ in $A$ ), or because its value can be derived by applying the constraints $C$ to the known assignments $A$ . The predicate extends to sets: $\text{Known}(\mathbf{X}) = \bigwedge_{x \in \mathbf{X}} \text{Known}(x)$ .

What Known captures: the transitive closure of deduction from the initial assignments through the constraints. If you know $x_0$ and $x_0 - 1 = y$ , then Known(y) is true even though $y$ isn't directly assigned in $A$ . This is the computational analogue of "can the model figure it out from what it's been given."

Definition 3.1: Underspecified CSP. A CSP is underspecified if and only if:

$\bigwedge_{j \in [M]} c_j(\mathbf{x}_j) \land A \implies \neg \text{Known}(y)$

In prose: given all the constraints and all the known assignments, the target variable $y$ is still not determinable. If this implication does not hold — meaning $y$ is determinable — the CSP is well-specified.

What this definition computes: it takes the conjunction of all constraints (which are assumed to hold) and all known variable assignments, and checks whether this conjunction logically forces the value of $y$ to be known. If not, there are at least two different assignments to the unknown variables that are both consistent with $A$ and $C$ but give different values for $y$ , so the model cannot determine which value is correct.

Why this form: this is the classical definition of determinability in constraint systems — a variable is determined iff every satisfying assignment to the CSP gives it the same value. The paper's "underspecified" is the negation: there exist at least two satisfying assignments that differ on $y$ . This is objective because satisfiability of constraints is a mathematical property, not a matter of interpretation.

Definition 3.2: Sufficient set. A set of variables $\mathbf{X} \subseteq X$ is a sufficient set (for $y$ ) if and only if:

$\bigwedge_{j \in [M]} c_j(\mathbf{x}_j) \land A \land \text{Known}(\mathbf{X}) \implies \text{Known}(y)$

In prose: if you additionally knew the values of all variables in $\mathbf{X}$ , the target variable $y$ would become determinable.

What this computes: this checks whether adding the assignments of variables in $\mathbf{X}$ to the known assignments $A$ is enough to make $y$ computable. Operationally, for each candidate sufficient set, you would add those variables' values to the known set, run constraint propagation or deduction, and check whether $y$ now has a unique value across all satisfying assignments.

Why this form: sufficiency defines what makes a clarifying question "correct." If the model asks about a variable in a sufficient set, and the user answers with its value, the model can then compute $y$ . The definition handles the possibility that $y$ might be determinable in multiple ways; any sufficient set represents a valid line of questioning. This is important because different problem formulations might have different paths to the answer — the model isn't penalized for finding an alternative sufficient variable that the dataset constructor didn't anticipate.

The optimization problem for efficient questioning. Among all sufficient sets, the paper defines the optimal question-asking strategy as finding the smallest one:

$\hat{\mathbf{X}} = \arg\min_{\mathbf{X} \subseteq X} |\mathbf{X}| \quad \text{s.t. } \mathbf{X} \text{ is sufficient}$

In plain language: ask about as few variables as possible while still being able to compute the answer once the user responds.

Why this objective: it formalizes the intuition that good question-asking is efficient — you don't ask for information you could derive yourself, and you don't ask for more information than necessary. In real deployments, each question has a cost (user time, cognitive load, potential for error), so minimizing the number of questions while maximizing informativeness is the natural objective.

Definition 3.3: 1-sufficient CSP. An underspecified CSP is a 1-sufficient CSP if the size of its smallest sufficient set is 1. The variable in a smallest sufficient set is called a sufficient variable of the problem.

What this means concretely: the problem is missing exactly one piece of information, and there exists at least one variable such that if you knew its value, you could compute the answer. There might be multiple sufficient variables (e.g., asking about $x$ would work, but asking about $z$ would also work), and choosing any of them is treated as correct in QuestBench.

Why 1-sufficient CSPs are the focus (Section 3.3). The paper argues that 1-sufficient CSPs are the natural building block for several reasons. First, evaluability: they can be cast as multiple-choice problems where the model selects one option, making evaluation straightforward and automatable. In contrast, $k$ -sufficient problems (with $k > 1$ ) require evaluating sequences of questions where each subsequent question depends on the answer to the previous one, creating a combinatorial explosion in evaluation complexity. Second, upper bound interpretation: performance on 1-sufficient CSPs provides "an approximate upper bound on a model's capacity for information acquisition, since any $k$ -sufficient CSP can become 1-sufficient after $k-1$ clarifying questions." If a model cannot handle the case where only one question is needed, it will certainly fail when multiple sequential questions are required. Third, difficulty diversity: even within the 1-sufficient constraint, the paper shows that problems span a wide range of difficulty as measured by the axes defined next.

Difficulty Axes of 1-Sufficient CSPs

The paper formalizes four properties that affect how hard a 1-sufficient CSP is to solve. These axes are defined based on the computational complexity of two reference algorithms — brute-force search and backwards search — since the paper hypothesizes that LLMs solving these problems must effectively perform some form of search through the CSP's variable-constraint graph.

Axis 1: $|X|$ — total number of variables. This is simply the count of all variables in the CSP. More variables means a larger search space, making it harder to identify which one is sufficient by random guessing or by enumerating candidates.

Axis 2: $|C|$ — total number of constraints. This counts the rules or equations relating variables. More constraints means more relationships to track when reasoning backward from the target variable or forward from the known assignments.

Axis 3: $d$ — depth of the backward search tree. Backwards search works by starting from the target variable $y$ and recursively finding which variables appear in constraints that involve $y$ , then which variables appear in constraints that involve those variables, and so on, building a tree rooted at $y$ . The depth $d$ is the number of recursive expansions needed before all sufficient variables are found. Deeper trees require longer chains of reasoning — the model must trace implications through multiple steps of the constraint graph.

Axis 4: $\mathbb{E}_{\text{BF}}$ — expected number of random guesses. This quantifies the expected effort if the model were to check variables one at a time (brute-force), guessing randomly without replacement. It is computed as:

$\mathbb{E}_{\text{BF}} = \frac{|X| + 1}{\mathfrak{s} + 1}$

where $\mathfrak{s}$ is the number of sufficient variables in the problem. For example, if there are 40 variables and 3 of them are sufficient, the expected number of guesses before hitting a correct one is $(40 + 1) / (3 + 1) = 10.25$ .

What this metric captures: it operationalizes how "diluted" the correct choices are among the total options. A problem where only one variable out of 60 is sufficient ( $\mathbb{E}_{\text{BF}} = 30.5$ ) is much harder to solve by blind guessing than one where 10 variables out of 15 are sufficient ( $\mathbb{E}_{\text{BF}} \approx 1.5$ ). Even with verification (checking each guess), the expected number of checks scales linearly with $\mathbb{E}_{\text{BF}}$ .

Relationship to search complexity (Table 4). The paper provides asymptotic runtime bounds for brute-force and backwards search in Logic-Q and Planning-Q expressed in terms of these axes. For Logic-Q, brute-force search is $O((|X| + |C|) \mathbb{E}_{\text{BF}} / \delta)$ with probability at least $1 - \delta$ — you multiply the cost of verifying one candidate (running constraint propagation, which costs $O(|X| + |C|)$ ) by the expected number of candidates you'll need to check before finding a correct one. Backwards search is $O(|X| |C|^d)$ — you expand the search tree through $d$ levels, with a branching factor of at most $|X| \cdot |C|$ (considering all subsets of variables that appear in each constraint). For Planning-Q, brute-force is $O(2^{2|X|} b^2 \mathbb{E}_{\text{BF}} / \delta)$ (double-exponential in the number of atoms, reflecting the state-space explosion of PDDL), while backwards search is $O(b^{2d})$ or $O(3^{|X| d})$ depending on whether you expand by actions or by states.

Why these axes are important for the paper's analysis: they provide a mechanism-independent way to characterize problem difficulty. If LLM accuracy correlates negatively with search depth or $\mathbb{E}_{\text{BF}}$ , this is evidence that the model is performing something analogous to search through the CSP, and that the difficulty of that search explains performance variation. If there is no correlation — as the paper finds for some models in Planning-Q — this suggests the model is using a qualitatively different strategy (Section 5.2 discusses this in detail).

Logic-Q Construction: From SimpleLogic to 1-Sufficient Propositional CSPs

Logic-Q is constructed from the SimpleLogic dataset (Zhang et al., 2023), which provides propositional logic problems about an imaginary person named Alice. The original SimpleLogic problems are well-specified: they provide a set of implicative rules (e.g., "If Alice is jittery and strange, then Alice is stubborn"), a set of known facts (e.g., "Alice is smart. Alice is not stubborn."), and a target question ("Is Alice pleasant?"). The transformation to 1-sufficient CSPs involves discarding the original known facts and constructing new partial assignments that require exactly one additional piece of information.

Step 1: CSP encoding. Each SimpleLogic problem is converted into a CSP as follows:

Variables $X$ : all properties of Alice that appear anywhere in the rules (e.g., "strange," "jittery," "worried," "pleasant"). Each variable has domain $D_i = \{\text{True}, \text{False}\}$ — properties are boolean.
Constraints $C$ : the rules expressed as implicative constraints. Each rule takes the form:

$C = \bigwedge_{i \in [M]} \left(\left(\bigwedge_{j \in [M_i]} x_{i,j}\right) \implies x_{i, M_i+1}\right)$

where $x_{i,j}$ are the premise variables and $x_{i, M_i+1}$ is the conclusion. For example, "strange $\land$ jittery $\implies$ stubborn" is one such constraint. The paper notes that these constraints can be rewritten as disjunctions (e.g., $\neg$ strange $\lor$ $\neg$ jittery $\lor$ stubborn) to allow deduction in multiple directions — from $\neg$ stubborn and jittery, you can infer $\neg$ strange.

Known assignments $A$ : initially empty in the Logic-Q construction; the original SimpleLogic $A$ is discarded.
Target variable $y$ : the property being asked about (e.g., "pleasant").

Step 2: Enumerating all assignments that imply $y$ is true or false (Section B.1.1). The paper uses recursive backwards search to compute two sets: $A^{(y)} = \{A^{(y)}_i : A^{(y)}_i \implies y\}$ (all partial variable assignments that force $y$ to be true) and $A^{(\neg y)} = \{A^{(\neg y)}_i : A^{(\neg y)}_i \implies \neg y\}$ (all partial assignments that force $y$ to be false).

The backwards search starts from the target and iteratively expands. Formally, beginning with $g_0 = y$ (the most trivial way to make $y$ true is to directly assert it), the algorithm finds all constraints whose conclusion is $y$ and adds their premises. For example, if rules $a \land b \implies y$ and $c \land \neg d \implies y$ exist, then $g_1 = (a \land b) \lor (c \land \neg d)$ . This disjunction of conjunctions means "either make $a$ and $b$ true, or make $c$ true and $d$ false."

The process recurses on each term in each conjunction: if a rule $e \land f \implies b$ exists, then the term $a \land b$ expands to $a \land (e \land f)$ . The distributive property is applied after each expansion to maintain a disjunction-of-conjunctions normal form. This continues until no further expansions are possible or a termination condition is met (e.g., a conjunction is fully expressed in terms of variables with no further implications).

What this computes: the full set of all possible combinations of property assignments that would logically force the target property to have a particular truth value. Any one of these conjunctions, if true, constitutes sufficient information to answer the question. The disjunction captures the fact that there are multiple independent ways to reach the same conclusion.

Step 3: Finding 1-sufficient assignment pairs (Section B.1.2). The algorithm examines all pairs $(A^{(y)}_i, A^{(\neg y)}_j)$ from the two sets and identifies pairs that differ in the assignment to exactly one variable $x_d$ . If such a pair exists, removing $x_d$ 's assignment from both creates a partial assignment $\tilde{A}$ where:

$\tilde{A} = (A^{(y)}_i \setminus x_d) \land (A^{(\neg y)}_j \setminus x_d)$

This $\tilde{A}$ has the property that $\text{Known}(x_d) \land \tilde{A} \implies \text{Known}(y)$ — knowing $x_d$ 's value is sufficient to determine $y$ 's value — but $\tilde{A} \implies \neg \text{Known}(y)$ — without $x_d$ , you cannot determine $y$ .

Verification step 1: ensure $\tilde{A}$ by itself doesn't already imply $y$ or $\neg y$ . If it did, then $x_d$ wouldn't actually be necessary — $\tilde{A}$ would already be sufficient. Such pairs are discarded.

Verification step 2: handle nested sufficient sets. If there exists another $\tilde{A}'$ such that $\tilde{A}' \implies \tilde{A}$ (i.e., $\tilde{A}'$ is a superset of $\tilde{A}$ 's assignments, making it logically stronger), then the sufficient variables of $\tilde{A}'$ are a subset of those of $\tilde{A}$ . However, resolving $\tilde{A}'$ might require shallower search than resolving $\tilde{A}$ because fewer constraints need to be traversed. To ensure the LM must conduct search to the full depth required by $\tilde{A}$ , the paper constructs an "invalid set" consisting of the sufficient variables of $\tilde{A}'$ — at test time, the model is told it cannot ask about these variables. This forces the model to engage with the deeper reasoning path.

Step 4: Multiple-choice option generation. The final Logic-Q problem consists of the rules in natural language, the partial assignment $\tilde{A}$ (the known facts), the target question, and a list of choices corresponding to all variables in $X$ plus "End questioning." The correct choices are the variables in the sufficient set $\mathcal{C}(\tilde{A})$ :

$\mathcal{C}(\tilde{A}) = \left\{x : \left(\text{Known}(x_d) \land \tilde{A} \implies \text{Known}(y)\right) \land \left(\tilde{A} \implies \neg \text{Known}(y)\right)\right\}$

What the model must do: given the rules, the known facts, and the fact that one property's value is missing, identify which property to ask about. Any sufficient variable is a correct answer. The model outputs either a question ("Is Alice [property]?") or "End questioning" if it determines no question is needed.

Data statistics (Table 1): Logic-Q contains 1,150 problems. The number of variables $|X|$ ranges from 10 to 59 (mean 37.9), search depth $d$ from 1 to 12 (mean 4.1), constraints $|C|$ from 8 to 108 (mean 47.8), and expected brute-force guesses $\mathbb{E}_{\text{BF}}$ from 1.2 to 15.0 (mean 6.1). No $b$ (blocks) dimension applies since there are no blocks.

Planning-Q Construction: From PDDL Blocks World to 1-Sufficient Planning CSPs

Planning-Q is constructed from the Blocks World domain via PyperPlan (Alkhazraji et al., 2020), a classic planning domain where blocks must be rearranged from an initial configuration to a goal configuration using four actions: pick-up, put-down, stack, and unstack.

Step 1: CSP encoding of planning. A fully-specified Blocks World problem with $b$ blocks is encoded as a CSP $\langle X, S, Q, s_0, y \rangle$ :

Variables $X$ : all possible atoms — predicates applied to specific blocks — that can be true or false in any state. These include (on a b), (ontable c), (clear d), (handempty), (holding e), and their negations. For $b$ blocks, the total number of ground atoms is $|X|$ , each with domain $D_i = \{\text{True}, \text{False}\}$ .
States $S$ : the set of physically possible fully-specified states (complete assignments to all variables in $X$ ). A state $s \in S$ is valid if it satisfies the domain physics — for example, no two blocks can be on top of the same block, the robot cannot be holding two blocks at once, etc.
Actions $Q$ : the four Blocks World action schemas instantiated with specific blocks: pick-up(?x), put-down(?x), stack(?x, ?y), unstack(?x, ?y). Each action has preconditions (atoms that must be true in the current state for the action to apply) and effects (atoms that become true or false in the next state). For example, unstack(?x, ?y) requires (on ?x ?y), (clear ?x), and (handempty) to be true; its effects make (holding ?x) and (clear ?y) true while making (on ?x ?y), (clear ?x), and (handempty) false.
Constraints $C$ : the action dynamics. For any action sequence $[q_t]_{t \in [n]}$ and corresponding state sequence $[s_t]_{t \in [n]}$ , each pair $(s_t, s_{t+1})$ must satisfy the precondition and effect constraints of $q_t$ . Formally, for all $p \in \text{pre}(q_t)$ , the previous state must imply $p$ ; for all $e \in \text{effects}(q_t)$ , the next state must imply $e$ .
Known assignments $A$ : the partial initial state $\tilde{s}_0$ — a subset of atoms whose truth values are known at the start.
Target variable $y$ : the optimal (shortest) action sequence from the initial state to a state satisfying the goal conditions. Six possible goal conditions were manually written by the authors, e.g., (on b a), (and (on b a) (on c b)), (and (on b a) (ontable a) (on d c) (ontable c)).

Why the target is the optimal sequence, not any sequence: as the paper notes, all initial states in Blocks World can reach any goal state through some sequence of actions (the domain is connected), so asking for any valid plan would make no information-gathering necessary — you could always produce a plan by, for instance, unstacking everything, clearing the table, and rebuilding from scratch. Constraining the target to the shortest path makes the problem non-trivial because different initial states have different shortest paths to the same goal, and the model must determine which one applies given the partial observations.

Step 2: Deriving well-specified partial states (Section B.2.1). The paper performs backwards breadth-first search from the goal conditions to find all partial initial states that have a unique optimal action sequence to the goal. Starting from $g_0 = \{[y]\}$ (the goal itself as a partial-state trajectory), the algorithm iteratively expands: for each partial-state trajectory $\tilde{\tau}$ in the current set $g_i$ , and for each action $q \in Q$ , it computes the partial state $\tilde{s}$ from which applying $q$ would transition to $\tilde{\tau}[0]$ (the first state of the trajectory). The new trajectory $[\tilde{s}, q] + \tilde{\tau}$ is added to $g_{i+1}$ . Expansion continues until a termination condition: a branch terminates when it arrives at a partial state implied by a previously encountered partial state (to avoid infinite regress).

The set of well-specified partial states $\tilde{\mathcal{S}}_0$ is the set of initial states from all these trajectories — each $\tilde{s}_0 \in \tilde{\mathcal{S}}_0$ has the property that there is a unique optimal action sequence $\hat{\tau}$ from any fully-specified state consistent with $\tilde{s}_0$ to the goal:

$\tilde{\mathcal{S}}_0 = \{\tilde{s}_0 : \exists \hat{\tau}, s_0 \in F(\tilde{s}_0) \implies \Psi(s_0) = \hat{\tau}\}$

where $F(\tilde{s}_0)$ is the set of all fully-specified states consistent with the partial state $\tilde{s}_0$ , and $\Psi$ is the optimal planner (implemented via breadth-first search on the state space).

Step 3: Creating 1-sufficient partial states (Section B.2.2). For each well-specified partial state $\tilde{s}_0 \in \tilde{\mathcal{S}}_0$ , the algorithm removes one atom $x_d$ to create a 1-sufficient candidate $\tilde{s}_0' = \tilde{s}_0 \setminus x_d$ . It then verifies:

No single-question cascade: check that there is no other well-specified partial state $\tilde{s}_0'' \in \tilde{\mathcal{S}}_0$ such that $\tilde{s}_0'' = \tilde{s}_0' \land x$ for some atom $x$ . If such a state exists, knowing that $x$ is true would bring us to $\tilde{s}_0''$ , which is well-specified — but this is still a 1-sufficient problem, not a problem with the property we want. The more critical case is when $x$ being false brings us to another 1-sufficient partial state, meaning we'd need two questions. To eliminate this, the paper explicitly sets $x$ to False in such cases.
At most two distinct optimal action sequences: for all fully-specified states $s_0' \in F(\tilde{s}_0')$ consistent with the candidate, count the number of distinct optimal action sequences to the goal. The paper requires $|\{\Psi_y(s_0'), \forall s_0' \in F(\tilde{s}_0')\}| \leq 2$ .
- If exactly one unique action sequence exists across all consistent states, the problem is actually well-specified — the missing atom doesn't affect the optimal plan. The model should answer "No questions needed."
- If exactly two unique action sequences $\tau_1, \tau_2$ exist, the paper partitions the consistent states into two groups $\tilde{S}_0^{(1)}$ and $\tilde{S}_0^{(2)}$ based on which optimal sequence they produce. It then identifies the differentiating attributes — atoms that are true in all states of $\tilde{S}_0^{(1)}$ but false in all states of $\tilde{S}_0^{(2)}$ , or vice versa. Asking about any of these differentiating attributes would disambiguate which optimal plan applies.

If the candidate passes both checks, the atom $x_d$ is confirmed as a sufficient variable — knowing its truth value fully determines the unique optimal action sequence.

Step 4: Multiple-choice question generation. The final Planning-Q problem includes the PDDL domain definition, the partially observed initial state (expressed as known atoms), the goal conditions, and a list of possible questions of the form "Is (predicate objects) true?" for all atoms in the domain, plus "No questions needed." The correct choices are the differentiating atoms identified in Step 3.

Data statistics (Table 1): Planning-Q contains 7,500 problems. Variables $|X|$ range from 25 to 64 (mean 46.0), search depth $d$ from 1 to 14 (mean 6.9), blocks $b$ (a domain-specific metric, not a general CSP property) from 4 to 7 (mean 5.7), and $\mathbb{E}_{\text{BF}}$ from 3.0 to 33.0 (mean 18.5). The number of constraints $|C|$ is not applicable in the same way as Logic-Q because the constraints are the PDDL action dynamics, which are fixed for the domain rather than varying per problem.

GSM-Q and GSME-Q Construction: From GSM-Plus to 1-Sufficient Math CSPs

The math domains are constructed from GSM-Plus (Li et al., 2024a), which extends GSM8k (Cobbe et al., 2021) by adding distractor information — variables and equations that are irrelevant to computing the answer. The construction involves human annotation to translate word problems into CSPs and then systematically remove one necessary variable assignment plus all distractor assignments.

Step 1: Human CSP annotation. The paper recruited 21 annotators to:

Identify and discard semantically ambiguous problems. Annotators first try to solve each GSM-Plus word problem. If the problem is ambiguous (multiple valid interpretations exist), it's discarded entirely. Examples of ambiguity that caused rejection include unclear antecedents ("10% of that" where "that" is unspecified), unclear temporal ordering ("was getting hungrier so she tripled" — before or after adding slices?), and missing assumptions (points per question in a quiz).
Parse well-specified problems into CSPs. For each unambiguous problem, three different annotators independently translate the word problem into a set of variables $X$ (each with domain $\mathbb{N}$ , the natural numbers), a set of equations $C$ (of two allowed forms: "assigns one variable to one constant" or "assigns one variable to a relation among other variables"), a set of known assignments $A$ (variables whose numerical values are directly stated in the problem), and a target variable $y$ (the quantity being asked for). The annotation guidelines (reproduced in Appendix B.3) emphasize that "a good rule of thumb is to have one variable stand in for every number in the problem" and to avoid equations that combine too many operations.
Automated verification. The annotated CSPs are checked automatically: the equations must be parseable and must actually yield the correct answer from GSM-Plus. Any CSP that fails parsing or produces a wrong answer is discarded. All valid CSPs are kept, including different CSPs corresponding to the same word problem (reflecting different but valid parses by different annotators).

Step 2: Making CSPs underspecified. Starting from a fully-specified CSP $\langle X, D, C, A, y \rangle$ , the paper withholds two types of variable assignments:

All distractor variables $\{d_i\}_{i=0}^n$ — variables from GSM-Plus that were never essential to computing $y$ . These are simply removed from $A$ .
One necessary variable assignment $a \in A$ — a variable that is required to compute $y$ (i.e., removing it makes $y$ undeterminable from $C$ and the remaining $A$ ). The removal creates a new partial assignment:

$\tilde{A} = A \setminus \left(\{d_i\}_{i=0}^n \cup \{a\}\right)$

The resulting CSP $\langle X, D, C, \tilde{A}, y \rangle$ is 1-sufficient: asking about the value of $a$ is sufficient to compute $y$ (since all other necessary assignments are still in $\tilde{A}$ ), but without $a$ , $y$ is not determinable.

Step 3: Symbolic and natural language variants. The underspecified CSPs form GSME-Q — the equation-based version where problems are presented symbolically. To create GSM-Q (the natural language version), annotators are shown the original GSM-Plus word problem and the CSP, and asked to rewrite the word problem to remove the necessary variable $a$ and all distractor variables $\{d_i\}_{i=0}^n$ . Each rewrite is checked for grammatical coherence, and the annotator verifies whether the answer to the rewritten question is "unclear" (indicating successful underspecification) or "different" from the original answer (indicating the rewrite accidentally made a different problem well-specified).

Data statistics (Table 1): GSM-Q contains 23,642 problems (but experiments use a representative subset of 288 due to evaluation budget). GSME-Q contains 6,590 problems (experiments use 151). Both domains have small variable counts ( $|X|$ from 2 to 27, mean 3.5), shallow search depth ( $d$ from 1 to 7, mean 2.1), few constraints ( $|C|$ from 1 to 9, mean 3.0-3.1), and moderate $\mathbb{E}_{\text{BF}}$ (2.5 to 18.5, mean 4.9-5.0). These metrics are substantially lower than Logic-Q and Planning-Q, explaining why models saturate performance on math but struggle on logic and planning.

Evaluation Protocol

The paper evaluates LLMs in three settings, all using the multiple-choice format where the model must select the correct question from a list of options.

Question-asking accuracy (Section 5.1). The primary evaluation metric is the fraction of problems where the model selects a correct sufficient variable. For each problem in QuestBench, the model is presented with the underspecified CSP in domain-appropriate natural language or symbolic form, along with a numbered list of possible questions. The possible questions include:

One option per variable in the domain (framed as "What is the value of [variable]?" or "Is Alice [property]?" or "Is (predicate objects) true?" depending on domain).
A "No questions needed" option (or "End questioning" in Logic-Q).

A response is correct if the model selects a variable that is in the sufficient set $\mathcal{C}$ , or if it selects "No questions needed" for problems that are actually well-specified (which occurs in Planning-Q where removing a non-differentiating atom results in the same optimal plan regardless). For Logic-Q, the model generates "Question: Is Alice [attribute]?" and answer matching extracts the chosen attribute.

Prompting strategies. The paper tests three prompting approaches:

Zero-shot (ZS): the model receives the problem description and the list of options, with instructions to reason step by step (if using chain-of-thought) and output the choice number or attribute name.
Zero-shot + Chain-of-Thought (ZS+CoT): the model is instructed to "reason step-by-step" before providing its final answer. This is enabled by appending "Please reason step-by-step, then generate 'Answer:' followed by the number" (Planning-Q/GSM-Q/GSME-Q) or similar (Logic-Q uses a different output format without explicit CoT prompting, but Gemini Flash Thinking 2.0 Exp 01-21 produces reasoning traces natively).
Four-shot (4S): the model is given four example problems with correct answers before the test problem. The paper does not detail the exact examples used, but they are presumably selected from the training split to be representative of the domain.

Models evaluated (Table 2). The experiments cover both proprietary and open-source models as of the evaluation period (06/2024 to 03/2025): GPT-4o, o1-preview, Claude 3.5 Sonnet, Gemini 1.5 Pro, Gemini 1.5 Flash, Gemini 2.0 Flash Thinking Experimental 01-21 (a reasoning-enhanced model), and Gemma 2 variants at 2B, 9B, and 27B parameters.

BFS baselines. To contextualize LLM performance, the paper includes breadth-first search (BFS) baselines that solve the CSPs algorithmically. BFS is run up to fixed depths of 3, 5, and 10 on each domain. At depth 10, BFS achieves 99.8% on Logic-Q, 93.9% on Planning-Q, and 100% on GSME-Q/GSM-Q (Table 2) — confirming that the problems are algorithmically solvable given sufficient search, and that the performance gap in LLMs is not due to inherent unsolvability.

Ablation: Well-specified reasoning (Section 5.3). To isolate question-asking ability from general reasoning ability, the paper constructs well-specified variants of QuestBench problems by restoring the missing variable assignment (in Logic-Q, the missing property value; in Planning-Q, the missing atom; in GSM-Q, the original GSM-Plus problem). Models are then evaluated on:

Logic-Q well-specified: determine whether the target property is true or false given all rules and all facts.
Planning-Q well-specified: produce a valid plan from the fully-specified initial state to the goal.
GSM-Q/GSME-Q well-specified: compute the numerical answer.

The paper then filters the question-asking evaluation to only include problems where the model correctly solved at least one corresponding well-specified variant (there may be multiple well-specified variants per QuestBench problem, corresponding to different possible restored values). The question-asking accuracy on this filtered subset is reported in Tables 5 and 6, along with the difference from unfiltered accuracy and the number of retained samples.

Ablation: Underspecification detection (Section 5.4). To assess whether models can even recognize when a problem is underspecified, the paper mixes well-specified and 1-sufficient variants of QuestBench problems. For each problem, the model must either provide the target variable's value (if the problem is well-specified) or output "Not sure" (if it's 1-sufficient). Performance is measured by F1 score on the "Not sure" class (Table 7), compared against a Random baseline where a proportional number of examples are randomly labeled "Not sure."

Cross-validation for difficulty-based analyses. The paper uses Spearman's rank correlation (Table 3) to measure the association between model accuracy and each difficulty axis. Statistical significance is assessed at $p < 0.05$ , with bolded values in Table 3 indicating significance and colored values indicating moderately strong correlations.

Why the Multiple-Choice Format?

The paper explicitly justifies the multiple-choice design (Section 6):

"We believe the multiple-choice format for evaluating question-asking is a necessary precursor to open-ended formats for question asking, since it is valuable for automated and rigorous evaluation. However, once a new approach makes open-ended evaluation viable and reliable, our benchmark can be readily used by simply omitting the multiple-choice options."

This reveals the research strategy: the multiple-choice format solves the evaluation problem — it provides an objective correctness signal that doesn't depend on human judgment or natural language generation quality — while the underlying CSPs remain valid evaluation targets for future open-ended question-asking systems. The benchmark is forward-compatible: the CSPs define the ground-truth sufficient set, and any system that identifies elements of that set through open-ended generation can be scored against the same standard.

The choice also addresses a practical issue identified in the literature: evaluating open-ended clarifying questions is difficult because "no universal 'right' question exists" (Section 2) in subjective or ambiguous domains. QuestBench sidesteps this by operating in domains where the "right" question is mathematically defined by the CSP structure, making multiple-choice both feasible and rigorous.

4. Key Insights and Innovations

Innovation 1: Formalizing Underspecification as a CSP Creates an Objective, Cross-Domain Evaluation Framework for Information Acquisition

The paper's most fundamental conceptual contribution is not the benchmark itself but the formal framework that makes rigorous evaluation of question-asking possible. Section 3.1-3.2 introduces a two-stage decomposition of reasoning tasks — parsing natural language into a CSP at Stage 1, then solving for the target variable at Stage 2 — and uses this decomposition to draw a clean boundary between semantic ambiguity (multiple valid CSPs could arise from parsing) and underspecification (the CSP is well-defined but missing variable assignments). Prior work extensively studied the former (Kuhn et al., 2023b; Zhang et al., 2024a; Min et al., 2020) but conflated it with the latter, or studied question-asking in subjective domains where no ground-truth correctness exists (Budzianowski et al., 2018; Li et al., 2023). By defining underspecification through a mathematical predicate — Known(y) is false given A and C (Definition 3.1) — and defining correctness of a clarifying question through the sufficiency property (Definition 3.2), the paper converts what was previously a subjective evaluation problem into an objective one. A question is correct if and only if knowing the answer to it makes the target variable determinable, and this property is decidable through constraint propagation and satisfiability checking. This is a fundamental shift in how information acquisition is evaluated: it replaces human judgment of question quality with mathematical verification of information sufficiency. The framework is domain-agnostic — it applies identically to propositional logic, PDDL planning, and algebraic math (compare Logic-Q's implicative constraints in Section B.1.1, Planning-Q's action dynamics in Section B.2.1, and GSM-Q's equations in Section B.3) — meaning the benchmark is extensible rather than ad-hoc. The significance extends beyond this paper: any future researcher constructing an information-acquisition task in a reasoning domain can use the ⟨X, D, C, A, y⟩ formalism to define what counts as a correct question, enabling objective evaluation without manual annotation of question quality. This is a theoretical and methodological innovation, not an incremental refinement of existing benchmarks.

Innovation 2: The Distinction Between Solving Well-Specified Problems and Identifying Missing Information Is an Empirically Demonstrated Capability Gap

The paper's most important empirical finding — and the one that justifies the benchmark's existence — is that question-asking is not merely a harder version of reasoning with sufficient information; it is a distinct capability that models can fail at even when they possess the underlying reasoning skills. Section 5.3 provides the decisive evidence through the filtered evaluation (Tables 5 and 6): when the paper restricts the question-asking evaluation to only those problems where the model correctly solved the corresponding well-specified variant, accuracy should approach 100% if question-asking were merely applying the same reasoning skills. Instead, in Logic-Q, filtering changes accuracy by at most 1.1 percentage points (Gemma 2 27B IT, ZS+CoT, +1.1%) across all models and settings, and the absolute accuracy remains far below ceiling — Gemini Flash Thinking 2.0 achieves only 37.4% on the filtered Logic-Q subset despite correctly solving 89.3% of the well-specified variants in ZS (Table 8). In Planning-Q, filtering improves accuracy somewhat (e.g., Claude 3.5 Sonnet goes from 7.53% to 11.3% in ZS), but the absolute numbers remain dismal — the best filtered accuracy is only 53.8% (Gemini Flash Thinking 2.0 in ZS, where it solved 53.5% of well-specified variants). This is a diagnostic finding with significant implications: it means that improving the underlying reasoning engine (e.g., through better pretraining or chain-of-thought) is not sufficient to improve question-asking, and that question-asking requires capabilities — such as reasoning about what information would be sufficient rather than what follows from given information — that current LLM training paradigms may not develop. Prior work largely assumed that question-asking ability would emerge from general reasoning ability (the dominant approach has been to prompt models with "ask clarifying questions" and hope reasoning capabilities transfer, e.g., Kuhn et al., 2023a; Zhang and Choi, 2023), but this paper provides the first systematic evidence that this assumption is false. The finding is not incremental — it changes what the field should optimize for, redirecting attention from general reasoning benchmarks to targeted information-acquisition training that the benchmark enables evaluating.

Innovation 3: The Difficulty Axes for 1-Sufficient CSPs Provide a Mechanism-Independent Way to Diagnose How Models Approach Information Acquisition

The paper's framework for characterizing problem difficulty — the four axes of |X|, |C|, d, and 𝔼_BF defined in Section 3.4 — is distinctive not because it proposes new metrics but because it connects problem structure to search algorithm complexity in a way that generates testable predictions about model behavior. By deriving asymptotic runtime bounds for brute-force and backwards search in each domain (Table 4, detailed in Appendix D), the paper creates a null hypothesis: if models are performing something analogous to algorithmic search, their accuracy should correlate negatively with the factors that increase search complexity. The correlation analysis in Section 5.2 (Table 3, Figure 4) then serves as a diagnostic. The results reveal domain-dependent patterns: in Logic-Q, most models show statistically significant negative correlations with all four axes (e.g., GPT-4o in ZS has correlations of -0.19 with d, -0.16 with |X|, -0.11 with |C|, and -0.26 with 𝔼_BF), consistent with models engaging in something like backwards search. In Planning-Q, correlations with d, |X|, and b are weak or non-significant for most models, but 𝔼_BF shows moderately strong negative correlations (e.g., -0.54 for o1-preview in ZS, -0.41 for Claude 3.5 Sonnet in 4S), suggesting models are verifying options one at a time (brute-force) rather than performing systemmatic backwards search through the state space. This is a new diagnostic capability: by changing the domain, the paper can infer what kind of computation the model is performing, not just how accurate it is. The finding in Planning-Q — that models' behavior resembles random guessing with verification rather than structured search — explains why chain-of-thought and few-shot prompting provide minimal gains in that domain (Table 2): if the model's strategy is essentially serial hypothesis testing, more thinking time doesn't help unless the model can simulate the planning dynamics more accurately, which it apparently cannot. This insight is fundamental rather than incremental because it provides a methodology for future work to diagnose model failures at the mechanistic level, something prior question-asking benchmarks (which lacked formal difficulty metrics) could not support.

Innovation 4: The Near-Random Underspecification Detection in Planning-Q Reveals a Systematic Failure of Epistemic Humility

The underspecification detection experiment in Section 5.4 (Table 7) produces a startling negative result: in Planning-Q, most models perform barely above the Random baseline at identifying when a problem is underspecified. The Random baseline achieves an F1 of 41.75% (when guessing "not sure" proportionally to the ground-truth rate of 41.8%). The best model, Claude 3.5 Sonnet in 4S, achieves only 31.52% — worse than random guessing. Most models score in the low single digits: GPT-4o achieves 1.23% F1 in ZS, Gemini Flash Thinking achieves 0.82%, Gemma 2 9B IT achieves 0.0%. The paper reports that "Gemini Flash Thinking, Claude 3.5, and GPT-4o predicted 'not sure' on only 1.4%, 4.6%, and 0.7% of cases in the zero-shot setting on Planning-Q, when the ground-truth ratio is 41.8%." This means models are systematically overconfident — they almost always attempt to produce a plan rather than admitting they lack information, and when they do admit uncertainty, they're often wrong about which problems are underspecified.

This finding is significant beyond raw performance because it identifies a qualitative failure mode that has safety implications. The paper notes in Appendix H that "improved question-asking abilities could be misused in automated persuasion" but frames the broader concern as epistemic humility being "increasingly important for alignment and safety." The Planning-Q results show that this humility is catastrophically absent in a domain that requires systematic state-space reasoning, even as models can detect underspecification modestly better in Logic-Q (F1 scores of 60.87% for Gemini Flash Thinking, 57.09% for Claude 3.5 Sonnet in ZS). The contrast between domains — reasonable detection in logic, near-random in planning — suggests that the ability to recognize one's own knowledge gaps is not a general capability but is tightly coupled to the domain's reasoning structure, and that current models have not developed it for domains requiring sequential, state-dependent reasoning. This is a diagnostic negative result with fundamental implications: it means that deploying LLMs in partially observable environments (robotics planning, multi-step decision-making) without explicit uncertainty quantification mechanisms is dangerous, because the models will confidently produce plans based on incomplete information rather than asking for clarification. The paper does not propose a solution, but the finding reframes the problem from "how do we make models ask good questions?" to "how do we make models recognize when they need to ask questions at all?" — a prerequisite that prior work largely assumed was already satisfied.

5. Experimental Analysis

Evaluation Methodology

Dataset. QuestBench comprises 1-sufficient CSP problems across four domains: Logic-Q (1,150 problems from SimpleLogic; Zhang et al., 2023), Planning-Q (7,500 problems from PyperPlan's Blocks World; Alkhazraji et al., 2020), GSM-Q (23,642 human-annotated underspecified grade school math problems, with experiments on 288 representative examples), and GSME-Q (6,590 equation-based equivalents of GSM-Q, with experiments on 151 representative examples). The reduction to representative subsets for GSM-Q and GSME-Q was done "in order to focus our evaluation budget on more difficult domains" (Section 5). All problems are presented as multiple-choice, where the model must select the correct clarifying question from options that include one per variable plus "No questions needed" or equivalent.
Base model(s). The paper evaluates both proprietary and open-source models as of the 06/2024 to 03/2025 evaluation window: GPT-4o (OpenAI, 2023), o1-preview (OpenAI), Claude 3.5 Sonnet, Gemini 1.5 Pro, Gemini 1.5 Flash, Gemini 2.0 Flash Thinking Experimental 01-21 (a reasoning-enhanced model), and Gemma 2 variants at 2B, 9B, and 27B parameter scales (Gemma Team, 2024). The selection spans multiple model families (Google, OpenAI, Anthropic), scales (2B to frontier-sized), and training paradigms (standard instruction-tuned, reasoning-optimized) to assess whether question-asking capability is a function of general model quality or requires something architecture- or training-specific. The Gemma 2 models provide the open-source baselines while the proprietary models represent near-SOTA capabilities at the time of evaluation.
Metrics. The primary metric is clarification question accuracy — the fraction of problems where the model selects a correct sufficient variable from the multiple-choice options. A choice is correct if the selected variable belongs to the sufficient set defined by the CSP formalization (Definition 3.2), or if the model selects "No questions needed" for well-specified variants (which occur in Planning-Q when the missing atom does not affect the optimal plan). For the underspecification detection ablation (Section 5.4), the metric is F1 score for the "Not sure" class in a binary classification setting (underspecified vs. well-specified). For the correlation analysis (Section 5.2), Spearman's rank correlation coefficient between model accuracy and difficulty axes is reported, with statistical significance assessed at p < 0.05. Accuracy and F1 are computed per-domain and per-prompt-setting (ZS, ZS+CoT, 4S).
Baselines. Two types of baselines are used. Algorithmic baselines include breadth-first search (BFS) run on each domain up to fixed depths of 3, 5, and 10 (Table 2). BFS at depth 10 achieves 99.8% on Logic-Q, 93.9% on Planning-Q, and 100% on GSME-Q and GSME-Q, establishing that the problems are algorithmically solvable with sufficient search and providing an upper bound on what a perfect algorithmic reasoner would achieve. Random baselines appear in the underspecification detection task (Table 7), where a "Random (proportional)" baseline guesses "Not sure" with probability equal to the ground-truth proportion of underspecified problems. For Planning-Q this is 41.75%, for Logic-Q 41.97%, for GSME-Q 42.90%, and for GSM-Q 50.0%. Additionally, the well-specified reasoning evaluation (Table 8) uses majority-class and simple heuristics implicitly — the models' performance on fully-specified variants serves as a ceiling for what question-asking could achieve if it were merely an application of general reasoning plus information-completeness.
Generation budget / compute accounting. This paper is a benchmark evaluation paper, not a scaling study, so there is no "generation budget" in the sense of trading sampling against accuracy. Models produce one response per problem (in some settings with chain-of-thought, one extended reasoning trace). The relevant resource accounting is evaluation budget: the authors explicitly note that "For GSM-Q and GSME-Q, we present results on a subset of 288 and 151 representative tasks, respectively, in order to focus our evaluation budget on more difficult domains" (Section 5). Compute details are provided in Appendix F: "Generating the dataset for the Logic-Q and Planning-Q mostly requires CPU resources to conduct the backwards search. The search and filtering stages for creating each domain required a few (between three to seven) days each. For experiments, we queried Gemini, GPT-4o, and Claude models through the API. We launched Gemma models on either TPU v5e node pools, or 1-2 H100 GPUs, and ran inference with them. Evaluating each model took a few hours for Logic-Q, up to a few days for Planning-Q, and a few minutes for GSM-Q / GSME-Q."
Cross-validation / statistical protocol. No cross-validation is employed because the benchmark is a fixed evaluation set — there is no hyperparameter tuning or strategy selection that would risk overfitting to the test set. The primary statistical protocol involves Spearman's rank correlation (Table 3) with significance testing at p < 0.05 (bolded values indicate significance). The paper also reports the number of samples retained in filtered evaluations (Tables 5, 6) to indicate statistical reliability. For the GSM-Q and GSME-Q representative subsets, the paper notes that a sanity check on the full datasets with GPT-4o (ZS) achieved 99.39% on GSME-Q and 84.05% on GSM-Q, confirming that "Performance saturates on the full set, consistent with our findings on the smaller subset in the paper" (footnote 9). This partial validation suggests the subset results are not artifacts of small sample size, though the subset selection methodology is not described in detail.

Main Quantitative Results

Overall Question-Asking Accuracy Across Domains

The headline finding from Table 2 is a sharp domain-dependent performance cliff: all models achieve over 80% accuracy on GSM-Q and GSME-Q but struggle to exceed 50% on Logic-Q and Planning-Q. The best model in each domain varies by prompt setting:

Logic-Q best performance: o1-preview in ZS achieves 49.91%. The next best is Gemini Flash Thinking 2.0 Exp 01-21 at 37.39% (ZS). Chain-of-thought and few-shot prompting provide minimal gains: Gemini Flash Thinking drops from 37.39% (ZS) to 34.61% (ZS+CoT), while Claude 3.5 Sonnet improves from 30.09% (ZS) to 36.78% (ZS+CoT). Four-shot provides mixed results — Gemini Flash Thinking achieves 38.43%, only marginally above its ZS score. No model breaks 50% in any setting.
Planning-Q best performance: Gemini Flash Thinking 2.0 Exp 01-21 achieves 47.32% (ZS), the highest across all models and settings. Claude 3.5 Sonnet reaches only 7.53% (ZS) but improves substantially with CoT to 34.03%. o1-preview achieves 42.31% (ZS). GPT-4o drops from 24.49% (ZS) to 16.36% (ZS+CoT) — a degradation suggesting that prompting for step-by-step reasoning can be counterproductive in this domain. The 4S setting produces the most dramatic variation: Gemini Flash Thinking drops from 47.32% (ZS) to 19.32% (4S), a 28-percentage-point collapse, while Claude 3.5 Sonnet holds steady at 34.56% (4S) compared to 34.03% (ZS+CoT). The Gemma 2 2B IT model performs near the floor: 10.76% (ZS), 3.01% (ZS+CoT), 7.51% (4S).
GSME-Q best performance: GPT-4o (ZS+CoT) achieves 99.34%. Gemini 1.5 Flash (ZS+CoT) reaches 98.68%. o1-preview (ZS) achieves 98.01%. Even the weakest models perform well: Gemma 2 2B IT achieves 90.73% in 4S. Performance largely saturates, with most models above 90% in multiple settings.
GSM-Q best performance: Claude 3.5 Sonnet (4S) achieves 94.10%. o1-preview (ZS) achieves 91.32%, matching Claude 3.5 Sonnet (ZS). GPT-4o (ZS+CoT) achieves 92.01%. Gemma 2 2B IT shows the widest variation: 49.65% (ZS), 68.40% (ZS+CoT), 37.50% (4S), suggesting the smallest model's capability is fragile and prompt-dependent even in the "easy" domain.

The BFS baselines contextualize these results: at depth 3, BFS achieves only 39.0% on Logic-Q and 5.75% on Planning-Q — meaning shallow search is insufficient. At depth 5, BFS reaches 80.6% on Logic-Q but only 27.2% on Planning-Q. At depth 10, BFS achieves 99.8% on Logic-Q and 93.9% on Planning-Q. This confirms that Planning-Q problems are algorithmically much harder (requiring deeper search for high coverage) and that current LLMs are operating at a level roughly comparable to BFS at depth 3-5 on Logic-Q and depth 3 on Planning-Q, depending on the model. The gap between what BFS can achieve with sufficient search and what LLMs achieve suggests that LLMs are either failing to perform sufficiently deep search, or are performing search incorrectly (e.g., following spurious reasoning paths).

Comparing GSME-Q to GSM-Q within the same models reveals that verbalized presentation systematically reduces accuracy despite identical underlying CSPs. Claude 3.5 Sonnet (ZS): 94.70% on GSME-Q vs. 91.32% on GSM-Q. Gemini 1.5 Pro (ZS): 48.34% on GSME-Q vs. 77.78% on GSM-Q — an exceptional case where verbal presentation helps, though the GSME-Q score is anomalously low for this model (it reaches 96.69% with CoT and 92.05% with 4S, suggesting the ZS symbolic prompting is particularly ill-suited to this model). GPT-4o (ZS+CoT): 99.34% on GSME-Q vs. 92.01% on GSM-Q. Gemma 2 9B IT (4S): 86.75% on GSME-Q vs. 55.56% on GSM-Q — the largest verbal-symbolic gap, indicating that smaller models are disproportionately affected by the translation from equations to words. The paper hypothesizes that "identifying missing information requires building up a search tree, which can be easier if the problem were presented symbolically than verbally" (Section 5.1), and these results are consistent with that hypothesis, though the Gemini 1.5 Pro anomaly suggests model-specific sensitivity to prompt format.

Correlation Between Problem Complexity and Accuracy

Table 3 and Figure 4 present Spearman's rank correlation coefficients between model accuracy and the four difficulty axes (search depth d, number of variables |X|, number of constraints |C|, and expected brute-force guesses 𝔼_BF) for each domain, model, and prompt setting. The results reveal domain-dependent correlation patterns that suggest different cognitive strategies.

Logic-Q correlations (Table 3, top block): Most models show statistically significant negative correlations with all four axes, though the strength varies. The consistently strongest correlation is with 𝔼_BF: for o1-preview (ZS), -0.41; for Gemini Flash Thinking (4S), -0.35; for Claude 3.5 Sonnet (ZS+CoT), -0.28. Search depth d shows the next strongest: -0.23 (o1-preview, ZS), -0.28 (GPT-4o, 4S), -0.22 (Gemini Flash Thinking, 4S). |X| and |C| show weaker but still significant correlations: typically in the -0.10 to -0.27 range. The consistent negative correlations across all axes, particularly with search depth and 𝔼_BF, are consistent with models performing something analogous to backwards search through the implication graph — deeper search trees and more variables/constraints make the search harder, and higher 𝔼_BF means more options must be checked before finding a sufficient variable. The moderate correlation strength (most |r| < 0.3) suggests that search-like reasoning explains only a fraction of the variance; other factors (rule structure, model-specific heuristics) likely account for the rest.

Planning-Q correlations (Table 3, second block): The pattern is qualitatively different from Logic-Q. Correlations with d, |X|, and b (number of blocks) are weak and mostly non-significant. For o1-preview (ZS): 0.01 (d), -0.06 (|X|), -0.06 (b). For Gemini Flash Thinking (ZS+CoT): -0.10 (d), -0.11 (|X|), -0.11 (b). For GPT-4o (ZS+CoT): 0.09 (d), -0.00 (|X|), -0.00 (b). None of these correlations are bolded (statistically significant) for these axes.

In stark contrast, 𝔼_BF shows moderately strong negative correlations for several models: o1-preview (ZS), -0.54; GPT-4o (ZS+CoT), -0.56; Claude 3.5 Sonnet (4S), -0.48; GPT-4o (4S), -0.41. These correlations are significant and substantially stronger than the correlations with |X| or b, even though 𝔼_BF is a function of |X| and the number of sufficient variables (𝔼_BF = (|X|+1)/(𝔰+1)). The paper interprets this pattern as evidence that "those LLMs' behavior might be analogous to randomly guessing, or verifying one choice at a time (the 𝔼_BF factor in Table 4 for brute-force search), but perhaps not using breadth-first search for verification" (Section 5.2). In other words, models appear to be engaging in serial hypothesis testing — picking a candidate variable, reasoning about whether it would resolve the underspecification (verifying), and moving on if it doesn't — rather than performing systematic backwards search from the goal state through the action dynamics. The verification step is non-trivial (it "can entail rolling out entire trajectories — potentially from multiple possible initial states"), but the absence of correlation with structural complexity metrics (d, |X|) suggests the enumeration strategy is essentially random or heuristic, not guided by the problem structure.

GSME-Q correlations (Table 3, third block): Correlations are generally weak and inconsistent across models. Gemini Flash Thinking (ZS) shows -0.21 (d), -0.24 (|X|), -0.24 (|C|), -0.24 (𝔼_BF) — all significant. Gemini 1.5 Pro (ZS+CoT) shows -0.34 (|C|) and -0.30 (|C| in 4S), the strongest individual correlations in this domain. But most models show non-significant correlations or very weak ones (e.g., GPT-4o, ZS: -0.10, -0.09, -0.25, -0.09). The weak correlations are consistent with performance saturation — when most models achieve >90% accuracy, floor effects mask difficulty-related variance.

GSM-Q correlations (Table 3, fourth block): Correlations are uniformly weak or non-significant. Almost no coefficients are bolded, and the magnitude is consistently below |0.20|. Exceptions: Gemini 1.5 Pro (ZS) shows -0.19 (|X|) and -0.19 (𝔼_BF), and Claude 3.5 Sonnet (ZS+CoT) shows -0.19 (|X|) and -0.19 (𝔼_BF), but none are bolded. This is expected given the near-saturation performance and the narrow range of difficulty in the math domains (|X| mean 3.5, d mean 2.1).

Figure 4 visualizes these correlations by plotting accuracy against binned values of each axis. The Logic-Q plots show clear downward trends across d, |X|, |C|, and 𝔼_BF for most models. The Planning-Q plots show flat or noisy trends for d, |X|, and b, but steeper negative trends for 𝔼_BF (particularly visible for o1-preview and GPT-4o). The GSME-Q and GSM-Q plots are compressed at high accuracy with little discernible trend, except at the extreme high ends of the axis ranges where accuracy sometimes drops for a few models.

Question-Asking vs. Well-Specified Reasoning: The Filtered Evaluation

The ablation in Section 5.3 constructs well-specified variants of QuestBench problems and evaluates models on both solving those variants (Table 8) and on question-asking restricted to problems where the model succeeded at the well-specified version (Tables 5 and 6). The central finding: success at the well-specified task does not translate to success at question-asking, particularly in Logic-Q and Planning-Q.

Well-specified accuracy (Table 8): models are substantially better at solving fully-specified variants than at asking questions. In Logic-Q, top performers include Gemini Flash Thinking (89.34% ZS, 88.64% ZS+CoT), Claude 3.5 Sonnet (64.08% ZS, 78.59% ZS+CoT), and Gemini 1.5 Pro (70.19% ZS, 74.74% ZS+CoT). In Planning-Q, performance is much lower: Gemini Flash Thinking achieves 53.46% (ZS) and Claude 3.5 Sonnet achieves 69.54% (ZS+CoT), but GPT-4o achieves only 14.12% (ZS+CoT) and Gemma 2 2B IT achieves 0.01% (ZS). In GSME-Q, multiple models achieve 100% with CoT (Claude 3.5 Sonnet, GPT-4o, Gemini 1.5 Flash). In GSM-Q, Claude 3.5 Sonnet reaches 100% (ZS+CoT) and Gemini Flash Thinking achieves 98.26% (ZS).

Logic-Q filtered question-asking (Table 5): Despite correctly solving 89.34% of well-specified variants, Gemini Flash Thinking 2.0 achieves only 37.4% question-asking accuracy on the filtered subset — a 0.0% improvement over the unfiltered accuracy of 37.39%. Claude 3.5 Sonnet (ZS+CoT), which solves 78.59% of well-specified variants correctly, reaches only 37.0% filtered question-asking accuracy (+0.2% over unfiltered). GPT-4o (ZS+CoT), at 76.33% well-specified accuracy, achieves 32.0% filtered accuracy (+0.4%). The number of retained samples is high for all models (typically 1,088-1,150 out of 1,150), meaning the filtering is not selecting an unusual subset. The takeaway is stark: even when models provably possess the deductive capability to solve the logic problem given complete information, they cannot identify which single piece of information they are missing. The gap between well-specified accuracy (~70-89%) and filtered question-asking accuracy (~25-37%) is 40-50 percentage points, and it is not closed by chain-of-thought or few-shot prompting.

Planning-Q filtered question-asking (Table 5): The picture is more nuanced because Planning-Q well-specified accuracy is lower, and filtering changes the retained sample size substantially. Gemini Flash Thinking (ZS), with 53.46% well-specified accuracy, achieves 53.8% filtered question-asking accuracy on 4,273 retained samples — a +6.5% improvement over unfiltered (47.32%). Claude 3.5 Sonnet (ZS+CoT), with 69.54% well-specified accuracy, achieves 43.4% filtered accuracy on 5,176 samples — a +9.4% improvement. GPT-4o (ZS+CoT), with only 14.12% well-specified accuracy, achieves 35.7% filtered accuracy on 1,339 samples — a +19.3% improvement (the largest absolute gain in the table). This pattern suggests that in Planning-Q, general reasoning ability does partially translate to question-asking ability: models that can plan better also ask better questions. However, the filtered accuracy remains far from 100% and, in most cases, far from chance-level for a model that truly understood information sufficiency. Even the best filtered accuracy (53.8%) indicates that on nearly half the planning problems the model can solve when fully specified, it cannot identify what information it needs to make them solvable.

GSME-Q and GSM-Q filtered question-asking (Table 6): In the math domains, filtering has larger effects due to the smaller subset sizes. Gemini 1.5 Pro (ZS) improves from 48.34% to 58.5% on GSME-Q (+10.1%) but with only 53 retained samples — the low sample count makes the estimate noisy. GPT-4o (ZS+CoT) maintains 99.3% on GSME-Q regardless of filtering (151 retained), consistent with saturation. In GSM-Q, Claude 3.5 Sonnet (ZS+CoT) achieves 91.0% on 288 retained samples (0.0% change), while Gemma 2 9B IT (4S) improves from 55.56% to 63.1% on 157 samples (+7.5%). Several models show small negative differences (Claude 3.5 Sonnet ZS on GSME-Q: -8.3% on 44 samples; Gemma 2 9B IT 4S on GSME-Q: -10.3% on 34 samples), likely reflecting sampling noise due to the tiny retained subsets rather than genuine degradation.

The critical implication across all domains: question-asking accuracy on the filtered subset is not 100% — and in Logic-Q, it's barely different from unfiltered accuracy. This means the model's failure at question-asking is not primarily due to inability to reason with the constraints once information is complete. It is a distinct meta-cognitive failure: the model cannot introspect on its own knowledge state to determine what is missing. This finding is robust across Logic-Q (high well-specified accuracy, low filtered question-asking accuracy, large sample sizes) and is the strongest empirical evidence for the paper's central claim that question-asking is a distinct capability from reasoning.

Underspecification Detection

Table 7 reports F1 scores for detecting whether a problem is underspecified when the model must answer the target variable's value if well-specified or respond "Not sure" if underspecified. The most striking result is the catastrophic failure in Planning-Q, where most models perform at or below random guessing.

Logic-Q detection (Table 7, first column): Gemini Flash Thinking (ZS+CoT) achieves 61.70% F1, Claude 3.5 Sonnet (ZS+CoT) achieves 58.87%, both above the Random baseline of 41.97%. Gemini 1.5 Pro (ZS+CoT) reaches 53.37%. However, GPT-4o (ZS) achieves only 36.26% — below random — and its ZS+CoT improves to 45.95%. The 4S setting is worse than ZS+CoT for most models: Gemini Flash Thinking drops from 61.70% to 57.95%, Claude 3.5 Sonnet drops from 58.87% to 51.65%. The Gemma models show weak performance overall (Gemma 2 2B IT: 35.96% F1 in ZS+CoT; Gemma 2 9B IT: 48.98% in ZS+CoT), though Gemma 2 2B IT achieves 47.03% in ZS — roughly at random — but degrades in CoT and 4S.

Planning-Q detection (Table 7, second column): The results border on catastrophic. The Random baseline achieves 41.75% F1. No model substantially exceeds random. The best is Gemma 2 2B IT in 4S at 46.52% — only ~5 points above random — but the same model achieves 0.00% in ZS and 0.05% in ZS+CoT, suggesting the 4S result may be an artifact of the few-shot examples rather than genuine uncertainty recognition. Claude 3.5 Sonnet (4S) achieves 31.52% — below random. Most models score in the low single digits: GPT-4o (ZS): 1.23%; Gemma 2 9B IT (ZS+CoT): 0.00%; Gemma 2 2B IT (ZS+CoT): 0.05%. The paper reports that "Gemini Flash Thinking, Claude 3.5, and GPT-4o predicted 'not sure' on only 1.4%, 4.6%, and 0.7% of cases in the zero-shot (no chain-of-thought) setting on Planning-Q, when the ground-truth ratio is 41.8%." This means models are overwhelmingly biased toward answering rather than admitting uncertainty, and even when they do admit uncertainty, their choices are no better than chance — they cannot distinguish underspecified from well-specified planning problems.

GSME-Q detection (Table 7, third column): Performance spans a wide range. Claude 3.5 Sonnet (ZS+CoT) achieves 96.58% F1 — near-perfect detection. Gemini 1.5 Flash (ZS+CoT) achieves 90.59%. But Gemini Flash Thinking (ZS+CoT) drops to 12.42% — far below random (42.90%). Gemma 2 2B IT (ZS) achieves 2.56% F1. The extreme variation suggests that detection ability is fragile and model-specific rather than robust across architectures. The Claude 3.5 Sonnet result (96.58% in ZS+CoT, 65.22% in ZS) indicates that chain-of-thought prompting dramatically improves detection for some models but not others.

GSM-Q detection (Table 7, fourth column): Performance is moderate. Claude 3.5 Sonnet (4S) achieves 86.41% F1. Gemma 2 9B IT (ZS+CoT) achieves 67.12%. But Gemini Flash Thinking (ZS+CoT) achieves only 28.57% — below random (50.0%). Gemma 2 2B IT (ZS) achieves 4.08% — the model essentially never says "Not sure" correctly. The pattern reinforces the domain-dependence: math problems are generally easier to detect as underspecified than planning problems, but even in math, performance is highly variable across models.

Cross-domain pattern: The detection results map onto the question-asking difficulty ordering. GSM-Q/GSME-Q (where question-asking accuracy is high) shows moderate-to-good detection for some models. Logic-Q (where question-asking is ~30-50%) shows detection moderately above random. Planning-Q (where question-asking is ~7-47%) shows detection at or below random for nearly all models. This progression suggests that the ability to recognize one's own knowledge gaps is a prerequisite for effective question-asking, and that Planning-Q's extreme difficulty stems from models' fundamental inability to even recognize when they lack information — they confidently hallucinate plans rather than acknowledging uncertainty.

The paper hypothesizes that "Planning-Q problems are sufficiently difficult that models cannot recognize uncertainty, and thus opt to guess randomly instead of answering (truthfully) that they are uncertain" (Section 5.4). The low base rate of "Not sure" responses (1.4-4.6% for the best models) supports this: rather than defaulting to uncertainty when confused, models default to overconfidence.

Ablation Studies and Robustness Checks

Prompting strategy variation (Table 2): The comparison across ZS, ZS+CoT, and 4S settings serves as an implicit ablation on the effect of additional reasoning time and examples. For Logic-Q, CoT provides minimal gains (Claude 3.5 Sonnet: +6.7 percentage points, GPT-4o: +4.2 points) and sometimes small losses (Gemini Flash Thinking: -2.8 points). 4S provides inconsistent effects (Gemini Flash Thinking: +1.0 point over ZS, but -2.9 points below ZS+CoT; GPT-4o: -1.8 points below ZS). For Planning-Q, the effects are more dramatic: CoT helps some models substantially (Claude 3.5 Sonnet: +26.5 points) but hurts others (GPT-4o: -8.1 points; Gemini Flash Thinking: -1.1 points). 4S generally underperforms ZS+CoT for the best models: Gemini Flash Thinking drops from 47.32% (ZS) to 19.32% (4S), a catastrophic 28-point decline. This negative result — that few-shot examples can dramatically hurt performance — suggests that Planning-Q problems have high structural variance that few-shot examples fail to capture, and that models may overgeneralize from limited examples in ways that produce systematic errors. The robustness finding is that no single prompting strategy dominates across domains or models, and the "obvious" strategy of providing more context or reasoning time cannot be assumed to help.
Symbolic vs. natural language presentation (GSME-Q vs. GSM-Q, Table 2): This comparison isolates the effect of problem format on question-asking, holding the underlying CSP constant. The consistent pattern is a symbolic advantage: most models perform better on GSME-Q than GSM-Q. Claude 3.5 Sonnet (ZS): 94.70% vs. 91.32% (-3.4 points). GPT-4o (ZS+CoT): 99.34% vs. 92.01% (-7.3 points). Gemma 2 9B IT (4S): 86.75% vs. 55.56% (-31.2 points — the largest gap). However, Gemini 1.5 Pro (ZS) reverses: 48.34% on GSME-Q vs. 77.78% on GSM-Q (+29.4 points). The anomaly is attributable to the GSME-Q ZS score being an outlier — Gemini 1.5 Pro reaches 96.69% on GSME-Q with CoT and 92.05% with 4S, so the ZS result likely reflects a failure to engage with the symbolic prompt format rather than inability to solve symbolic problems. The broader finding is that verbally presented underspecified problems are harder for most models, consistent with the hypothesis that "identifying missing information requires building up a search tree, which can be easier if the problem were presented symbolically than verbally" (Section 5.1). This is a practical robustness concern for deploying question-asking systems with natural language inputs.
Filtered evaluation as an ablation on reasoning-dependence (Tables 5, 6): This is the most theoretically important ablation. By restricting question-asking evaluation to problems where the model succeeded at the well-specified variant, the paper isolates whether question-asking failure is due to (a) inability to reason with the constraints even when complete, or (b) inability to identify missing information despite possessing the reasoning capacity. The finding that Logic-Q filtered accuracy barely changes (differences of 0.0-1.1 percentage points) while well-specified accuracy is 50-89% establishes that (b) is the dominant failure mode — the model has the reasoning capacity but cannot deploy it for information-acquisition. In Planning-Q, filtering produces larger gains (+6-19 points), suggesting both (a) and (b) contribute, but the filtered accuracy ceiling (max 53.8%) still demonstrates substantial (b)-type failure even when (a) is controlled for. The number of retained samples provides a robustness check: in Logic-Q, sample sizes remain large (1,088-1,150 out of 1,150) for all models, ensuring the results are not artifacts of subset selection. In Planning-Q, sample sizes vary from 73 (Gemma 2 9B IT, ZS+CoT) to 5,176 (Claude 3.5 Sonnet, ZS+CoT), but the consistent pattern of sub-54% accuracy across both large and small subsets suggests the finding is robust.
Underspecification detection F1 as an ablation on uncertainty recognition (Table 7): This ablation tests whether question-asking failure stems from models' inability to even detect that information is missing, separate from knowing which information is missing. The Planning-Q results — near-random F1 scores, "Not sure" response rates of 0.7-4.6% — demonstrate that the detection step itself is broken in this domain. In Logic-Q, detection is better (F1 36-61%) but still far from perfect, and the models that detect underspecification best (Claude 3.5 Sonnet, Gemini Flash Thinking in ZS+CoT) are also the best at question-asking (Table 2). This establishes a correlation between detection and question-asking ability, consistent with detection being a necessary precursor. A robustness concern: the "Random (proportional)" baseline is generous — a truly random baseline where the model guesses "Not sure" with probability proportional to the ground-truth rate will achieve the reported F1, but an even simpler baseline (always guess "well-specified," i.e., never say "Not sure") would achieve F1 of 0. By this baseline, many models in Planning-Q are performing comparably to "never express uncertainty," which is substantially worse than random proportional guessing and indicates a systematic bias toward overconfidence.
Full-dataset sanity check on GSM-Q and GSME-Q (Footnote 9, Section 5.1): The paper reports that GPT-4o (ZS) evaluated on the full GSM-Q (23,642 problems) achieves 84.05% accuracy and on the full GSME-Q (6,590 problems) achieves 99.39%. These are close to the representative-subset results (GSM-Q: 86.81% on 288; GSME-Q: 96.69% on 151), confirming that the subset is representative and that the near-saturation performance is not an artifact of small sample selection. This is an important robustness check given that the representative subsets are an order of magnitude smaller than the full datasets, though the subset selection methodology is not described in detail.
BFS depth as an algorithmic difficulty calibration (Table 2, bottom rows): The inclusion of BFS baselines at depths 3, 5, and 10 serves as a calibration of problem difficulty independent of model behavior. BFS depth 10 achieves 99.8% on Logic-Q, confirming that the problems are solvable by systematic search and that the ~50% accuracy ceiling for LLMs is not a data quality issue. BFS depth 5 achieves only 27.2% on Planning-Q, confirming that Planning-Q problems are algorithmically much harder (requiring deeper search) and that LLM performance around 7-47% is not evidence of model incompetence relative to algorithmic baselines at comparable search depth — BFS at depth 3 achieves 5.75% on Planning-Q, and many LLMs substantially exceed this.
Qualitative reasoning trace analysis (Appendix E): While not a controlled ablation, the paper includes reasoning traces from Gemini 2.5 Pro (a newer model not in the main evaluation) on one Logic-Q and one Planning-Q problem. The Logic-Q trace (Appendix E.1) reveals that the model performs extensive forward chaining and backward chaining, exhaustively exploring implication paths, but focuses only on proving the target variable is true, never investigating the negative direction (what would prove the target variable is false). The paper notes: "it appears that while the LM thoroughly investigates the positive direction (what is needed to establish that Alice is tired), it never investigates the negative direction (what is needed to establish that Alice is not tired). Thus, it did not identify the most informative question." This is a concrete, mechanistic diagnosis of a failure mode — asymmetry in search direction — that the quantitative metrics alone would not reveal. The Planning-Q trace (Appendix E.2) shows the model correctly identifying the minimal resolving information through spatial reasoning about block configurations rather than formal state-space search, consistent with the weak correlations between Planning-Q accuracy and search depth/|X| found in Table 3. These traces are anecdotal but suggest specific directions for improving model reasoning (e.g., enforcing symmetric forward/backward search in logic, incorporating formal state-space search in planning).

Critical Assessment

The paper's central claims map to the experiments as follows:

Claim: Current LLMs achieve only 40-50% accuracy on Logic-Q and Planning-Q while saturating performance on GSM-Q and GSME-Q (over 80%). The empirical evidence supports this claim directly. Table 2 shows Logic-Q accuracy ranging from 0.09% (Gemma 2 2B IT, ZS) to 49.91% (o1-preview, ZS), with most strong models in the 25-38% range. Planning-Q accuracy ranges from 3.01% (Gemma 2 2B IT, ZS+CoT) to 47.32% (Gemini Flash Thinking 2.0, ZS), with most strong models in the 7-42% range. GSME-Q and GSM-Q accuracy are above 80% for all strong models, with multiple models exceeding 90-99%. The domain gradient is clear and robust across models, prompt settings, and scales.

However, what these numbers actually demonstrate is narrower than the claim suggests. The "40-50%" ceiling applies to the best models (o1-preview, Gemini Flash Thinking) in their best settings. For most models in most settings, the ceiling is substantially lower — Claude 3.5 Sonnet (ZS) achieves 30.09% on Logic-Q and 7.53% on Planning-Q; GPT-4o (ZS) achieves 27.39% and 24.49%. The claim's phrasing ("they achieve only 40-50% accuracy") somewhat overstates typical performance, which for most models is 25-35% on Logic-Q and substantially worse on Planning-Q. Additionally, the 40-50% band includes o1-preview, which may have been specifically optimized for reasoning in ways that other models were not, so this represents an optimistic upper bound rather than a typical result.

A more precise restatement would be: the best-performing models in their best settings approach 50% on Logic-Q and 47% on Planning-Q, while typical strong models (Claude 3.5 Sonnet, GPT-4o, Gemini 1.5 Pro) operate in the 7-38% range depending on domain, prompt setting, and model, and GSM-Q/GSME-Q are largely saturated.

Claim: Question-asking requires more than the ability to reason with sufficient information, demonstrated by the filtered evaluation where models fail at question-asking even when they can solve the well-specified problem. The Logic-Q results provide strong support. Well-specified accuracy for top models is 64-89%, filtered question-asking accuracy is essentially unchanged from unfiltered (differences of 0.0-1.1 percentage points), and the retained sample sizes are large (1,088-1,150). This demonstrates that the model's failure is not due to inability to handle the logic — it demonstrably can — but due to inability to identify what information is missing.

However, there is a subtle methodological choice that affects interpretation. The filtered evaluation counts a problem as "retained" if the model correctly solved at least one corresponding well-specified variant. But a QuestBench problem may have multiple well-specified variants (corresponding to different values of the missing variable), and solving one variant correctly does not guarantee that the model would solve the variant with a different missing value — it may have succeeded on the well-specified variant by chance or by exploiting spurious correlations. This means the filtering is a necessary but not sufficient condition for the model possessing the relevant reasoning capability for that specific problem instance. The claim that "models possess the reasoning capability" therefore has a gap: the model may have gotten lucky on the well-specified version, or may have reasoning capability for one value of the missing variable but not another. A stricter test would be to require the model to solve all corresponding well-specified variants correctly, which would reduce sample sizes but provide stronger evidence that reasoning capability truly exists and is not being deployed for question-asking.

For Planning-Q, the filtered evaluation results are more ambiguous. Well-specified accuracy is much lower (0-70%), meaning many problems are filtered out, and the retained sample sizes vary enormously (from 1 for Gemma 2 2B IT ZS to 5,176 for Claude 3.5 Sonnet ZS+CoT). The filtered question-asking accuracy does improve (+6 to +19 points), suggesting that reasoning ability partially explains question-asking performance. But the ceiling remains low (max 53.8%), meaning even after controlling for reasoning ability, models fail on ~46% of planning problems. This is evidence that question-asking requires something beyond planning ability, but it's weaker than the Logic-Q case because the baseline reasoning ability is lower and the sample sizes are more variable.

Claim: Models struggle to detect underspecification, particularly in Planning-Q where they perform at or below random. The Planning-Q F1 scores in Table 7 provide strong support. The Random baseline achieves 41.75%. The best model F1 is 46.52% (Gemma 2 2B IT 4S), most models score in the single digits, and the base rate of "Not sure" responses is 0.7-4.6% when 41.8% of problems are underspecified. This is a genuine negative result that reveals a systematic overconfidence bias.

A weakness: the F1 metric may obscure important variation. The extremely low "Not sure" response rates mean F1 is driven by a tiny number of true positives and is highly sensitive to noise. A model that says "Not sure" on only 1-2% of problems but happens to be correct on those rare occasions could achieve a misleadingly high (or low) F1. Reporting precision and recall separately would clarify whether low F1 reflects failure to identify underspecified problems (low recall) or failure to be correct when expressing uncertainty (low precision). The paper's reporting of the "Not sure" response rates partially addresses this — the near-zero rates indicate a recall problem — but precision is not reported.

The cross-domain comparison is also informative: Logic-Q detection is substantially better than Planning-Q detection (F1 36-61% vs. 0-46%), and this maps onto the question-asking accuracy ordering. This correlation supports the paper's implicit claim that uncertainty detection and information-acquisition are linked, but the evidence is correlational, not causal. An experiment that explicitly manipulates detection ability (e.g., by prompting models to be more conservative about expressing uncertainty) and measures the effect on question-asking accuracy would strengthen the causal claim.

Claim: The correlation between problem complexity (difficulty axes) and accuracy reveals domain-dependent reasoning strategies — search-like in Logic-Q, brute-force verification in Planning-Q. The Spearman correlations in Table 3 provide moderate support for Logic-Q (consistent negative correlations with d, |X|, |C|, 𝔼_BF across most models) and weaker but still patterned support for Planning-Q (strong negative correlations with 𝔼_BF, weak/non-significant correlations with d, |X|, b). The interpretation that this reflects different reasoning strategies is plausible but speculative — correlation does not imply mechanism, and the paper does not perform direct interventions to test whether models are actually performing search or brute-force verification. The qualitative trace in Appendix E.2, showing a Planning-Q model solving through spatial visualization rather than formal search, is consistent with the interpretation but is a single example.

The correlations themselves are weak-to-moderate (most |r| < 0.3 for Logic-Q, except 𝔼_BF which reaches -0.41 for o1-preview). This means the difficulty axes explain only a small fraction of the variance in model accuracy — typically less than 10% for most axes. The paper acknowledges this implicitly by noting that the axes are "moderately good approximations for the type of reasoning LLMs are required to perform" (Section 5.2), but this limits the strength of the mechanistic interpretation. Other factors — the specific structure of the implication graph, the presence of distractors, the model's prior knowledge about the domain — likely dominate the variance.

What experiments would have strengthened the paper:

Open-ended question generation evaluation. The paper acknowledges (Section 6) that the multiple-choice format is a simplification, but does not include even a pilot evaluation of open-ended question generation. Since the CSP formalism defines the sufficient set, open-ended responses could be scored by checking whether the generated question asks about a variable in that set (modulo natural language variation). This would demonstrate that the benchmark's evaluation methodology extends beyond multiple choice, as the paper claims is possible. Without this demonstration, the practical utility of the formal framework for evaluating open-ended systems remains hypothetical.
Cross-model analysis of reasoning traces. The paper includes only two qualitative traces from Gemini 2.5 Pro (Appendix E). A systematic analysis of reasoning traces across models — categorizing failure modes (wrong search direction, incomplete search, spurious constraints, overconfidence) — would provide stronger evidence for the mechanistic interpretations in Section 5.2. The fact that the Logic-Q trace reveals an asymmetry in search direction suggests that such analysis could be highly diagnostic, but the paper does not pursue it systematically.
Training or fine-tuning interventions. The paper demonstrates that question-asking is a distinct capability from reasoning, but does not test whether it can be improved through targeted training. An experiment that fine-tunes a model on question-asking tasks (using the CSP formalism to generate training data) and measures transfer to held-out domains would transform the paper from a purely diagnostic contribution to one that also provides a path forward. The paper's claim that it provides "evaluation infrastructure and formal framework that makes rigorous study of question-asking possible" is well-supported, but the infrastructure is not yet demonstrated to enable improvement.
Scaling analysis. The paper evaluates models across scales (Gemma 2 2B, 9B, 27B), but does not systematically analyze how question-asking accuracy scales with model size within a model family. The Gemma 2 results (Table 2) show non-monotonic scaling in some cases: on Logic-Q ZS, 2B achieves 0.09%, 9B achieves 26.00%, 27B achieves 29.39% — clear scaling. But on Planning-Q ZS+CoT, 2B achieves 3.01%, 9B achieves 10.27%, 27B achieves 9.96% — non-monotonic. A systematic scaling analysis would reveal whether question-asking is an emergent capability that requires a critical model size, or whether it scales smoothly with general capability. This is particularly relevant given the paper's focus on "current LLMs" and the implication that future, larger models might solve these tasks — a claim that requires scaling evidence to evaluate.
Statistical confidence on the filtered evaluation. The filtered evaluation (Tables 5, 6) reports accuracy differences from unfiltered performance, but does not report confidence intervals or statistical significance for these differences. In several cases (particularly GSM-Q/GSME-Q with small retained sample sizes of 7-53), differences of 5-20 points could easily arise from sampling noise. Reporting confidence intervals, or at minimum noting which differences are statistically significant, would prevent overinterpretation of noisy estimates.
A truly random baseline for question-asking. The paper does not report a random-choice baseline for the primary question-asking task. A model that chooses uniformly among the multiple-choice options would achieve 1/(number of choices) accuracy. For Logic-Q, with a mean of 37.9 choices, random chance would be ~2.6%. This would contextualize whether the ~30-50% performance represents meaningful above-chance capability or near-floor performance. The 𝔼_BF axis partially captures this (lower 𝔼_BF means fewer guesses needed), but a direct random-choice baseline would be clearer.

Where the claims hold conditionally:

The claim that question-asking is distinct from reasoning holds most strongly for Logic-Q, where well-specified accuracy is high, filtered accuracy is unchanged, and sample sizes are large. For Planning-Q, the claim holds with the qualification that general planning ability does partially explain question-asking performance (filtering improves accuracy), but a substantial gap remains. For GSM-Q/GSME-Q, the claim is difficult to evaluate because performance is near ceiling, leaving little room to observe a gap between well-specified and question-asking accuracy — the claim may not be testable in these domains with current model capabilities.

The claim that models exhibit domain-dependent reasoning strategies (search vs. verification) holds conditionally on the assumption that correlation with difficulty axes implies mechanism — an assumption that the qualitative traces support but do not prove. The claim is best viewed as a hypothesis generated by the data rather than a conclusively demonstrated finding.

The claim that Planning-Q underspecification detection is catastrophic holds robustly across models, but the specific numerical ceiling (F1 ~0-46%) should be interpreted cautiously given the low base rate of "Not sure" responses and the consequent sensitivity to noise. The qualitative conclusion — models are systematically overconfident in Planning-Q — is well-supported; the precise F1 numbers are less reliable.

6. Limitations and Trade-offs

1. Single Benchmark Family and Single Model Architecture

The assumption or constraint. All experiments are conducted exclusively on the MATH benchmark-derived domains (Logic-Q from SimpleLogic, Planning-Q from Blocks World via PyperPlan, GSM-Q/GSME-Q from GSM8k/GSM-Plus) using models from a limited set of instruction-tuned transformer architectures. The paper does not evaluate on other reasoning domains (code generation, scientific QA, multi-step decision-making), other input modalities, or model architectures beyond the transformer family. The benchmark itself is constructed entirely from existing well-specified reasoning tasks by algorithmically removing information — it does not include naturally underspecified problems drawn from real-world usage.

The authors are transparent about this scope in Appendix G:

"our domains were chosen for their clear CSP formalizations, but may not capture the full range of naturalistic language understanding and ambiguity found in everyday tasks."

The consequence. The headline finding — that question-asking is a distinct capability from reasoning, and that models perform poorly on Logic-Q and Planning-Q but well on GSM-Q/GSME-Q — may be domain-specific rather than a general property of LLM information-acquisition ability. The sharp difficulty gradient (over 80% on math, under 50% on logic and planning) could reflect the fact that math word problems are heavily represented in LLM pretraining data, while propositional logic problems about imaginary people named Alice and PDDL planning problems are not. If models have simply memorized patterns for identifying missing variables in grade-school math formats but lack exposure to logic and planning formats, the performance gap reflects training data coverage rather than a fundamental cognitive limitation. Conversely, if the math results were achieved through shallow pattern matching rather than genuine information-acquisition reasoning, the paper may overestimate model capability even in the "easy" domains. The absence of evaluation on domains like code generation (where the model could ask about missing function arguments or ambiguous specifications) or scientific reasoning (where the model could request missing experimental parameters) means the framework's generalizability to other reasoning modalities is unverified.

What evidence exists in the paper. The paper provides no cross-domain transfer experiments. The four domains in QuestBench all derive from formal reasoning tasks with clean CSP representations, and the paper does not test whether a model fine-tuned on Logic-Q question-asking transfers to Planning-Q, or whether performance on one domain predicts performance on another. The fact that the difficulty axes (d, |X|, |C|, 𝔼_BF) explain only a small-to-moderate fraction of the variance in accuracy (Table 3, most |r| < 0.3 for Logic-Q, weaker for Planning-Q) suggests that domain-specific factors beyond the CSP structure — potentially including the surface form, the model's training data exposure, and the learned heuristics for different problem types — dominate the remaining variance. This is a limitation of inference, not measurement: the paper cannot distinguish whether models fail on Planning-Q because the information-acquisition task is inherently hard, or because the PDDL formulation is unfamiliar.

Mitigation status. The authors acknowledge the domain limitation in Appendix G as a scope consideration. Section 6 suggests extending the benchmark to "complex, real-world tasks like medical diagnosis and intent elicitation" as future work but does not attempt even a pilot evaluation in a different domain to test generalizability. The formal framework (CSP definitions, difficulty axes) is designed to be domain-agnostic, which provides a path for future extension, but the current empirical findings are confined to the four QuestBench domains. A practitioner deciding whether to use similar information-acquisition evaluation in a new domain would need to replicate the full benchmark construction pipeline (backwards search, 1-sufficiency verification, multiple-choice generation) with no guarantee that the behavioral patterns observed in this paper will transfer.

2. Difficulty Estimation Cost Is Unaccounted for in Deployment-Relevant Metrics

The assumption or constraint. The paper evaluates LLMs on identifying the correct question from a fixed set of multiple-choice options. This format enables rigorous evaluation by providing an objective correctness standard — the model selects from among candidate variables, and correctness is determined by whether the selected variable belongs to the mathematically-defined sufficient set. However, this format also embeds a hidden assumption: that the set of candidate questions is pre-enumerated and provided to the model. In a deployment setting, a system would need to either generate questions from scratch or generate and filter candidate questions itself. The paper does not evaluate open-ended question generation, and the multiple-choice format provides the model with information that would not be available in practice — namely, the full list of all possible variables in the problem, which narrows the search space considerably.

The authors acknowledge this explicitly in Section 6:

"We believe the multiple-choice format for evaluating question-asking is a necessary precursor to open-ended formats for question asking, since it is valuable for automated and rigorous evaluation. However, once a new approach makes open-ended evaluation viable and reliable, our benchmark can be readily used by simply omitting the multiple-choice options."

The consequence. The reported accuracies (e.g., 49.91% on Logic-Q, 47.32% on Planning-Q for the best models) are likely upper bounds on what the same models would achieve in an open-ended question-generation setting. In the multiple-choice format, the model can eliminate obviously irrelevant variables by inspection, perform verification on the most promising candidates, and use the list itself as a form of external memory. In open-ended generation, the model would need to identify the relevant variable space from the problem description, generate candidate questions, and evaluate their sufficiency — all without external scaffolding. The moderate-to-strong negative correlations with 𝔼_BF (expected brute-force guesses, Table 3) are particularly relevant here: 𝔼_BF captures how many random guesses among the provided choices would be needed to find a correct answer. In an open-ended setting, the effective 𝔼_BF would be larger because the model must generate the option space itself. If current models' question-asking behavior is well-approximated by serial verification of candidate variables (as the Planning-Q correlation pattern suggests), the removal of a pre-enumerated candidate list would increase the expected cost of finding a sufficient question proportionally to the model's inability to generate relevant candidates — a factor the current evaluation does not measure.

Furthermore, the "No questions needed" option in the multiple-choice format is an explicit signal that the problem might be well-specified. In an open-ended setting, a model must determine for itself whether any question is needed — a capability the underspecification detection experiment (Section 5.4, Table 7) shows is severely deficient, especially in Planning-Q where models almost never express uncertainty. The multiple-choice format may inflate the "No questions needed" accuracy relative to what would be observed in an open-ended setting, because the presence of the option prompts the model to consider the possibility, whereas an open-ended model might default to generating a question even when none is needed (or vice versa).

What evidence exists in the paper. No open-ended evaluation is conducted. The paper provides no comparison between multiple-choice and open-ended question generation, even as a pilot experiment. The qualitative trace in Appendix E.2, where Gemini 2.5 Pro correctly identifies the minimal resolving question in Planning-Q, suggests that at least some models can identify sufficient variables without seeing a pre-enumerated list for simple problems, but this is a single example. The underspecification detection results (Table 7) provide indirect evidence of the gap: models that cannot reliably detect whether a problem is underspecified would likely struggle to decide whether to generate a question at all in an open-ended setting, regardless of their multiple-choice accuracy.

Mitigation status. The paper treats the multiple-choice format as a deliberate simplification for rigorous evaluation, not as an oversight. Section 6 argues that the format is a "necessary precursor" and that the benchmark is forward-compatible with open-ended evaluation. However, no roadmap or methodology for transitioning to open-ended evaluation is provided — the paper simply notes that the CSP formalism could support it. This limitation is partially mitigated by the upstream-downstream distinction the paper draws: rigorous evaluation is a prerequisite for developing methods, and the multiple-choice format enables that evaluation. But for a practitioner deciding whether to deploy a question-asking system today, the paper provides no evidence about how the multiple-choice results translate to open-ended performance, which is the setting that matters in practice.

3. The 1-Sufficient CSP Simplification Excludes Realistic Multi-Question Dialogues

The assumption or constraint. QuestBench is restricted to 1-sufficient CSPs — problems where exactly one variable's value is missing and sufficient to determine the target. This is a deliberate design choice motivated by evaluability: 1-sufficient problems can be cleanly cast as multiple-choice, avoiding the combinatorial complexity of evaluating multi-question sequences. However, the authors are explicit that this is a simplification:

"QuestBench focuses exclusively on 1-sufficient CSPs, isolating the minimal case of information acquisition. However, real-world problems often include multiple missing pieces of information or more complex dependency structures." (Appendix G)

The consequence. The benchmark cannot evaluate a model's ability to plan a sequence of clarifying questions, where each subsequent question depends on the answer to previous ones. In practice, many underspecified reasoning problems require this: a medical diagnosis might require asking about symptoms, then based on the response, asking about medication history, then based on that response, asking about allergies. The paper's claim that "performance on 1-sufficient CSPs provides an approximate upper bound on a model's capacity for information acquisition" (Section 3.3) assumes that multi-question performance is monotonic in single-question performance — a model that excels at 1-sufficient CSPs will also excel at k-sufficient CSPs, all else being equal. This assumption is untested. It is possible that the skills required for multi-question information gathering (maintaining state across dialogue turns, updating beliefs based on partial answers, planning an efficient questioning strategy) are distinct from those required for single-question identification, and that performance on 1-sufficient problems overestimates multi-question capability.

More subtly, the 1-sufficient simplification also constrains the difficulty axes. The search depth d in 1-sufficient CSPs captures the depth of the backwards search tree from the target variable to the sufficient variable chain, but does not capture the combinatorial complexity of selecting which variables to ask about when multiple are missing and the questions interact (e.g., asking about variable A might make asking about variable B redundant, or might change which subsequent question is most informative). The difficulty axes in the current paper are defined for the 1-sufficient case and cannot characterize these interaction effects.

What evidence exists in the paper. No evaluation of k-sufficient CSPs is conducted. The paper does not test whether models that perform well on 1-sufficient problems can handle 2-sufficient or 3-sufficient variants of the same domains. The paper also does not provide evidence for the monotonicity assumption — it is stated as a rationale for the 1-sufficient focus, not empirically validated. The difficulty diversity within the 1-sufficient case (Table 1: search depths up to 14, up to 59 variables, up to 108 constraints) demonstrates that even the simplified problem is far from trivial, but this does not address whether the simplification itself distorts the capability being measured.

Mitigation status. The authors acknowledge the limitation explicitly (Appendix G, Section 6). Section 6 outlines k-sufficient CSPs as a natural extension: "This can be done by holding out k variable values, instead of just one, to construct k-sufficient CSPs" and notes that "it is crucial to consider whether the evaluation is for selecting all k questions simultaneously (in a batch), selecting them sequentially (one by one), or a combination of the two." However, no such extension is implemented, and the practical challenges — simulating user responses to intermediate questions, evaluating correctness of question sequences, handling the combinatorial space of possible question orderings — are flagged but not addressed. A practitioner interested in multi-turn information gathering would need to build their own evaluation infrastructure on top of the CSP formalism, with no guidance from the paper on how the 1-sufficient results might extrapolate.

4. The 14× Larger Model Baseline for the Training-Inference Tradeoff Is Never Tested

The assumption or constraint. The paper frames question-asking as a distinct capability from reasoning, demonstrated through the filtered evaluation (Section 5.3) where models fail at question-asking even when they can solve the corresponding well-specified problem. However, the well-specified evaluation (Table 8) uses the same base models as the question-asking evaluation — there is no comparison against a substantially larger model to test whether scaling model size closes the question-asking gap independently of well-specified reasoning ability. This is not a direct limitation of the benchmark design (which is primarily an evaluation contribution), but it constrains the strength of the paper's central claim that question-asking "requires more than the ability to reason with sufficient information" (Section 1).

The paper does not provide evidence about whether a sufficiently large model — perhaps an order of magnitude larger than the largest tested (o1-preview, Gemini 2.0 Flash Thinking) — would exhibit emergent question-asking capability that scales differently from well-specified reasoning. The Gemma 2 scaling comparison (2B → 9B → 27B) shows non-monotonic patterns in some settings (Planning-Q ZS+CoT: 3.01% → 10.27% → 9.96%), and the jump from 27B to frontier-scale models (~hundreds of billions of parameters) is not systematically studied.

The consequence. The paper cannot distinguish between two competing interpretations of its central finding: (1) question-asking is a fundamentally distinct cognitive capability that no amount of scaling within the transformer paradigm will elicit without targeted training, or (2) question-asking is an emergent capability that requires a larger model scale than the ones evaluated, and the current models are simply below the emergence threshold. The first interpretation motivates developing specialized training methods for information acquisition; the second interpretation suggests patience and scaling. The paper provides no evidence to favor one over the other. The fact that o1-preview (a reasoning-optimized model) achieves the best Logic-Q performance (49.91%) but still falls below 50% suggests that even frontier-scale reasoning models have not developed robust question-asking, but this is a single data point and does not constitute a scaling analysis.

Additionally, the well-specified reasoning evaluation (Table 8) shows that models are far from perfect even on the fully-specified variants. Logic-Q well-specified accuracy maxes out at 89.34% (Gemini Flash Thinking, ZS); Planning-Q at 69.54% (Claude 3.5 Sonnet, ZS+CoT). This means there is significant headroom for improving underlying reasoning ability. If a future model achieved near-100% well-specified accuracy, would its filtered question-asking accuracy also approach 100%? The paper's claim that question-asking is distinct from reasoning rests on the observation that filtering does not improve question-asking accuracy in Logic-Q — but the filtered models are still operating at 64-89% well-specified accuracy, not 100%. The claim would be stronger if it showed that even a model with perfect well-specified accuracy fails at question-asking, but no such model exists in the current evaluation.

What evidence exists in the paper. The paper provides three data points on scaling within the Gemma 2 family. Gemma 2 2B achieves 0.09% on Logic-Q ZS, 9B achieves 26.00%, 27B achieves 29.39% — a clear improvement from 2B to 9B but an almost-flat result from 9B to 27B. Gemma 2 2B achieves 10.76% on Planning-Q ZS, 9B achieves 14.36%, 27B achieves 7.64% — non-monotonic and actually lower for the largest model. These three points are insufficient to characterize scaling trends, especially since the model family is not designed for scaling-law analysis (the 2B/9B/27B variants may differ in training data, optimization, or architecture in ways beyond parameter count). No comparison across model families at comparable parameter counts is provided (e.g., GPT-4o vs. Gemini 1.5 Pro vs. Claude 3.5 Sonnet have unknown and likely different parameter counts, making cross-family scaling analysis impossible).

Mitigation status. The paper does not attempt to address this limitation. The authors do not claim that the current models represent a scaling limit, and the paper is framed as a benchmark contribution rather than a scaling-law analysis. However, the strong claim that question-asking "requires more than the ability to reason with sufficient information" is partially qualified by the absence of evidence about whether scaling would change this conclusion. A practitioner wondering whether to invest in specialized question-asking training vs. simply waiting for larger models would find no guidance in the paper. The open-source Gemma 2 results suggest that even a 30× increase in parameters (2B → 27B) produces inconsistent improvements in question-asking accuracy, but this is too narrow a scaling range to draw conclusions about emergent capabilities that might appear at the frontier scale.

5. The Planning-Q Underspecification Detection Failure Undermines the Practical Viability of Partial-Observability Deployments

The assumption or constraint. Planning-Q is constructed from the Blocks World domain, a classic but simplified planning environment. The paper evaluates models on their ability to ask the right question to disambiguate the optimal plan. The underspecification detection experiment (Section 5.4, Table 7) reveals a catastrophic failure: in Planning-Q, models almost never express uncertainty (0.7-4.6% "Not sure" response rate vs. 41.8% ground-truth underspecification rate), and when they do, their F1 scores are at or below random (max 46.52% for Gemma 2 2B IT in 4S). The authors acknowledge that models "cannot recognize uncertainty, and thus opt to guess randomly instead of answering (truthfully) that they are uncertain" (Section 5.4).

The consequence. This failure has direct safety implications for deploying LLMs in partially observable environments. A model that cannot detect when it lacks information will confidently produce a plan based on incomplete observations — potentially an unsafe or incorrect plan — rather than asking for clarification. In the Planning-Q setting, the consequence is benign (an incorrect block-stacking plan), but in higher-stakes domains (robotics navigation, medical treatment planning, financial decision-making), executing an uninformed plan could cause material harm. The paper's detection results suggest that current LLMs lack the epistemic humility required for safe operation under partial observability, and that this deficiency is most severe in domains requiring sequential, state-dependent reasoning — precisely the domains where partial observability is most common.

More subtly, the detection failure interacts with the question-asking evaluation itself. If a model cannot detect underspecification, then its question-asking accuracy on the multiple-choice task (where the "No questions needed" option and the candidate list are provided) may overestimate its capability in a real deployment. In practice, a model would need to both detect that a question is needed and identify the correct question. The detection experiment shows the first step is broken in Planning-Q; the multiple-choice question-asking evaluation implicitly provides this first step (by presenting the problem as one where a question might be needed, with an explicit "No questions needed" option), potentially inflating accuracy relative to what an unaided model would achieve.

What evidence exists in the paper. Table 7 provides strong evidence for the Planning-Q detection failure. The near-zero "Not sure" response rates (1.4% for Gemini Flash Thinking, 4.6% for Claude 3.5 Sonnet, 0.7% for GPT-4o in ZS) are particularly damning because they indicate a systematic bias toward overconfidence, not just random guessing. The models are not uncertain about whether they are uncertain — they are confident that they have enough information, even when they don't. The contrast with Logic-Q detection (F1 36-61%, "Not sure" response rates not reported but presumably higher given the F1 scores) shows that this bias is domain-specific, consistent with the interpretation that Planning-Q's state-space complexity makes it impossible for models to track their own knowledge boundaries.

The paper also provides indirect evidence through the question-asking results themselves: the fact that Planning-Q question-asking accuracy is so low (7-47%, Table 2) while the BFS baseline at depth 10 achieves 93.9% suggests that models are not just failing to ask the right question — they may not even be attempting a systematic question-asking strategy, instead falling back on heuristics or random guessing. This is consistent with the detection failure: if you don't know you're missing information, you can't ask a strategic question to acquire it.

Mitigation status. The paper identifies this as a concerning finding but does not propose solutions. Appendix H notes that "improved question-asking abilities could be misused in automated persuasion" and that "coupling queries with rationales for the model's query may allow user greater control over the information shared," but this addresses the opposite problem (models asking too many questions) rather than the demonstrated problem (models not asking questions when they should). The paper's framing of the benchmark as a diagnostic tool is appropriate, but the diagnostic reveals a failure mode that the paper does not begin to address. A practitioner deploying an LLM in a partially observable planning domain would learn from this paper that their model is likely overconfident and will not ask for clarification, but would receive no guidance on how to mitigate this failure — whether through fine-tuning, prompt engineering, uncertainty quantification methods, or architectural changes.

6. The CSP Formalization Assumes a Closed World of Known Variables and Constraints

The assumption or constraint. The entire QuestBench framework — from the definitions of underspecification (Definition 3.1) and sufficient sets (Definition 3.2) to the algorithmic construction of benchmark instances (Appendices B.1-B.3) — assumes that the set of variables $X$ , constraints $C$ , and domains $D$ are known and fixed. A problem is underspecified if and only if the known assignments $A$ are insufficient to determine $y$ given the known constraints. This formalization cannot express uncertainty about whether the right constraints are being used, whether additional unknown variables exist, or whether the domain of some variable is incorrectly specified.

In the benchmark construction, this assumption is implemented literally: the backwards search algorithms enumerate all possible assignments and constraint applications within a fixed CSP structure. The sufficient variables are those from the known set $X$ whose values, if added to $A$ , would make $y$ determinable via the known constraints $C$ . There is no mechanism for a model to question whether a constraint is missing, whether a variable not in $X$ needs to be introduced, or whether the CSP encoding itself is incorrect.

The consequence. The benchmark evaluates a restricted form of information acquisition: identifying which known unknown needs to be resolved. It does not evaluate the ability to identify unknown unknowns — variables or constraints the user never mentioned and the model has no reason to suspect exist, but which are necessary to solve the problem. In real-world deployments, users often omit information they don't realize is relevant, or describe problems using incomplete or incorrect mental models. A useful question-asking system should not only identify which of the mentioned variables needs a value, but also detect when the entire framing is insufficient and request reformulation. The CSP framework provides no formalism for this capability.

Concretely, consider a medical diagnosis scenario: the user describes symptoms (variables), the model has medical knowledge (constraints), and the target is the diagnosis. A missing symptom value is a known unknown — the model can ask "what is the value of this symptom?" and the CSP framework handles this. But if the relevant variable is a lab test the user never thought to mention, or a constraint about drug interactions the model's knowledge base doesn't include, the CSP framework offers no way to represent or detect these gaps. The model would incorrectly conclude the problem is well-specified (because all known variables would determine the diagnosis), when in fact the known variables are insufficient and the model needs to ask about variables outside the given set.

What evidence exists in the paper. The paper does not test this limitation because the benchmark is constructed by design to operate within a closed CSP world. The construction pipeline (Sections B.1-B.3) takes existing well-specified reasoning problems, converts them to CSPs, and withholds information — it never introduces genuinely novel variables or constraints that weren't present in the original formulation. The multiple-choice options are always subsets of the known variables in the CSP. The paper provides no evaluation of whether models can detect when the CSP formulation itself is incomplete or incorrect.

The human annotation process for GSM-Q/GSME-Q (Section B.3) touches on this issue indirectly: annotators discard problems that are "semantically ambiguous" — where the natural language admits multiple valid CSP parses. This filtering removes cases where the closed-world assumption breaks down at the parsing stage, but does not address cases where the well-specified CSP itself is missing constraints or variables needed to solve the real-world problem it's modeling.

Mitigation status. The paper does not address this limitation. The CSP formalization is presented as the definition of underspecification, not as an approximation that might break down in open-world settings. The authors note in Appendix G that the "domains were chosen for their clear CSP formalizations" — acknowledging that not all reasoning tasks admit clean CSP encodings, but not addressing the deeper issue that even within CSP-encodable tasks, the closed-world assumption may be violated in practice. Section 6 suggests extending to k-sufficient CSPs as future work, but this extension would operate within the same closed-world framework, simply withholding more variables from the known set rather than questioning the completeness of the set itself. A practitioner deploying question-asking in an open-world domain (e.g., customer support, where users describe problems using incomplete mental models) would find that the QuestBench framework provides no evaluation methodology and no empirical evidence about model behavior when the variable space is not pre-enumerated.

7. Implications and Future Directions

How This Work Changes the Landscape

This paper does not propose a new model, training algorithm, or prompting technique. It changes the landscape by creating the infrastructure that makes rigorous study of question-asking possible in the first place. Before QuestBench, evaluating an LLM's ability to ask clarifying questions meant either (a) evaluating in subjective domains where no ground-truth "correct" question exists, making quantitative comparison impossible, or (b) hand-crafting a small number of examples with ad-hoc correctness criteria, making systematic analysis and replication infeasible. The paper's CSP formalization — defining underspecification through the Known predicate (Definition 3.1) and question correctness through sufficiency (Definition 3.2) — converts what was a qualitative, domain-specific evaluation problem into a quantitative, domain-agnostic one.

The magnitude of this shift is methodological rather than paradigmatic. It does not overturn any existing theory of LLM reasoning; it fills a gap that the field had largely worked around. The dominant paradigm for LLM evaluation assumes well-specified problems (GSM8k, MATH, SimpleLogic, Blocks World), and the dominant paradigm for question-asking assumes subjective or ambiguous tasks (MultiWOZ, preference elicitation). QuestBench creates a third category — underspecified reasoning tasks with objective correctness — that neither paradigm addressed. This is a reframing of the evaluation problem rather than a reframing of LLM capabilities, but it is a reframing with teeth: the paper's empirical results show that the gap between these paradigms is not a smooth continuum but a cliff, and that models that appear competent under the well-specified paradigm fail systematically under the underspecified one.

The reconciliation of prior contradictions is one of the paper's most concretely useful contributions, even though it is implicit rather than argued. Prior work on LLM self-correction and question-asking produced contradictory findings — some studies showed LLMs could ask useful questions (Andukuri et al., 2024; Grand et al., 2024) while others showed they could not (Huang et al., 2023, on self-correction; the Planning-Q detection results in this paper). The paper's domain-dependent results (over 80% on GSM-Q/GSME-Q, under 50% on Logic-Q/Planning-Q) provide a resolution: question-asking ability is not a unitary capability but a domain-specific one, and prior contradictory findings reflect evaluation on different (implicitly difficulty-biased) problem distributions. A study that tested question-asking on grade-school math would conclude models are competent; a study that tested on PDDL planning would conclude they are not. Both are correct for their domains, and QuestBench provides the language (CSP structure, difficulty axes) to characterize which domains elicit which behavior.

The research directions this paper makes more attractive are those that treat information acquisition as a trainable, evaluable skill rather than an emergent property of general reasoning. Before QuestBench, a researcher wanting to improve question-asking had no standardized benchmark to measure progress — they could evaluate on subjective tasks with noisy human judgments or construct small custom test sets. QuestBench provides a large, diverse, automatically-evaluable benchmark with clear difficulty metrics, making it possible to run controlled experiments on question-asking training, compare methods quantitatively, and diagnose failure modes through the difficulty axes. The paper makes less attractive the research direction of simply scaling models and hoping question-asking emerges — the results show that o1-preview and Gemini Flash Thinking, frontier reasoning models as of early 2025, still fail to exceed 50% on Logic-Q, and that scaling Gemma 2 from 2B to 27B produces inconsistent, sometimes regressive improvements (Planning-Q ZS+CoT: 3.01% → 10.27% → 9.96%). If question-asking were an emergent capability that appears at scale, these frontier models would show stronger signals; the evidence suggests targeted training will be necessary.

The paper also redirects the conversation around epistemic humility and model uncertainty. Prior work on uncertainty estimation for LLMs has largely focused on semantic uncertainty — does the model know the answer, or is it uncertain about factual recall? (Kuhn et al., 2023b). QuestBench introduces a different axis: structural uncertainty — does the model recognize that it lacks necessary constraints or variable assignments to determine the answer, even when all the facts it knows are certain? The Planning-Q detection results (Table 7, F1 ~0-46%, "Not sure" response rates of 0.7-4.6%) show that this capability is nearly absent in current models for complex domains, while the Logic-Q detection results (F1 36-61%) show it is present but weak for simpler domains. This redirects uncertainty research from "does the model know the answer?" to "does the model know what it needs to know?" — a prerequisite for safe deployment in partially observable environments that prior benchmarks did not isolate.

Follow-Up Research This Work Enables

Training question-asking models using the CSP formalism as a data generation engine. The paper's CSP construction pipeline (Appendices B.1-B.3) can generate arbitrary numbers of 1-sufficient problems in any domain that admits a CSP encoding, without human annotation. This enables large-scale supervised fine-tuning: given a CSP ⟨X, D, C, ̃A, y⟩ where ̃A is the partial assignment with one sufficient variable x_d withheld, the training target is the set of sufficient variables C(̃A) (Equation 2). A strong follow-up would train a model (e.g., Gemma 2 9B) on 10,000-100,000 synthetic 1-sufficient CSPs from the Logic-Q generation pipeline, evaluate on the held-out QuestBench Logic-Q test set, and measure whether accuracy approaches the BFS depth 10 upper bound (99.8%, Table 2). The key question is whether training on procedurally generated CSPs transfers to the benchmark's natural-language instantiations of the same CSPs — the model must learn to map from rules-in-English to CSP structure, identify the sufficient variable, and map back to a natural-language question. A negative result (training improves CSP-form accuracy but not natural-language accuracy) would indicate that the bottleneck is parsing, not search; a positive result would demonstrate that the CSP formalism is not just an evaluation tool but a training curriculum.

Open-ended question generation and evaluation using the sufficient-set ground truth. The paper explicitly leaves open-ended evaluation as future work (Section 6), but the CSP formalism makes it tractable: the sufficient set C(̃A) defines which variables are correct to ask about, so an open-ended question is correct if it asks about any variable in C(̃A). A follow-up study would prompt models to generate free-form clarifying questions (without multiple-choice options), parse the generated question to identify which variable it asks about, and score correctness against C(̃A). This requires solving the parsing problem — mapping "What is the value of the number of eggs Janet started with?" to the CSP variable x_0 — which is non-trivial but solvable with modern LLMs in constrained domains. The key measurement is the gap between open-ended accuracy and multiple-choice accuracy on the same QuestBench problems. If open-ended accuracy is substantially lower (e.g., multiple-choice 50% → open-ended 20% on Logic-Q), this quantifies the hidden scaffold the multiple-choice format provides and establishes a realistic baseline for open-ended question-asking systems. If the gap is small, the multiple-choice format is validated as a reasonable proxy, and open-ended evaluation can proceed using the same CSP ground truth.

Combining question-asking with downstream task performance in a closed loop. QuestBench evaluates question-asking in isolation — the model asks one question, receives no answer, and is scored on whether the question was sufficient. A more ecologically valid evaluation would close the loop: given the underspecified CSP, the model asks a question; the user simulator (implemented by looking up the withheld variable's value) answers; the model then computes the target variable; accuracy is scored on the final answer. This setup would distinguish between models that ask a sufficient question but then fail to use the answer correctly (a downstream reasoning failure) and models that ask an insufficient question but get lucky with downstream reasoning. The paper's filtered evaluation (Section 5.3) partially addresses this by linking question-asking to well-specified reasoning accuracy, but does not simulate the full interactive loop. A follow-up implementing this closed-loop evaluation on QuestBench would measure end-to-end accuracy and decompose errors into question-selection failures vs. answer-computation failures, providing a more complete picture of models' interactive reasoning capabilities.

Stress-testing the difficulty axes with adversarial problem construction. The paper identifies four difficulty axes (d, |X|, |C|, 𝔼_BF) and correlates them with model accuracy (Section 5.2, Table 3), but the correlations are weak-to-moderate and domain-dependent. A strong follow-up would construct adversarial QuestBench-style problems designed to maximally stress specific axes while holding others constant — for example, a Logic-Q variant where d is systematically varied from 1 to 20 while keeping |X| and |C| fixed, to measure the precise scaling of model accuracy with search depth. The paper's dataset construction pipeline (Section B.1) already supports this: the backwards search algorithm naturally generates problems at different depths, and filtering by depth while sampling is straightforward. The key prediction is whether model accuracy drops exponentially with depth (consistent with tree search) or follows a different functional form (suggesting non-search mechanisms). A negative result — accuracy is uncorrelated with depth in this controlled setting — would undermine the paper's interpretation that difficulty axes capture search-like behavior and suggest that the correlations in Table 3 are epiphenomenal. A positive result — a clean exponential relationship — would validate the axes as genuine difficulty drivers and provide a predictive model of question-asking hardness.

Extending the benchmark to k-sufficient CSPs with sequential question evaluation. The paper identifies k-sufficient CSPs as the natural extension (Section 6) but does not implement them due to evaluation complexity. A follow-up would construct 2-sufficient and 3-sufficient CSPs using the same backwards-search pipeline (withholding 2-3 sufficient variables instead of 1), implement a user simulator that answers questions with ground-truth values, and evaluate models on their ability to ask a sequence of questions that makes the target variable determinable. The key metrics are (a) whether the model asks the right number of questions (neither over-asking nor under-asking), (b) whether the questions are asked in an efficient order (minimizing the number of questions needed before the target is computable), and (c) whether the model knows when to stop asking. This would test the paper's monotonicity assumption — that 1-sufficient performance upper-bounds k-sufficient performance — and reveal whether the additional complexity of multi-turn information gathering introduces qualitatively new failure modes (e.g., failure to track what has already been asked, asking redundant questions, or terminating prematurely). The Planning-Q domain is particularly interesting for this extension because its state-space complexity makes partial observability natural, and the current detection results suggest models will struggle to know when they have enough information to stop asking.

Cross-domain transfer and training curriculum design. The paper shows that models perform well on GSM-Q/GSME-Q but poorly on Logic-Q/Planning-Q, but does not test whether training on one domain transfers to another. A follow-up would fine-tune a base model on 1-sufficient CSPs from the Logic-Q pipeline and evaluate on Planning-Q, and vice versa. Positive transfer would suggest that the CSP formalism captures a domain-general question-asking skill — identifying sufficient variables in a constraint graph — that can be learned from examples in one domain and applied in another. Negative transfer (or no transfer) would suggest that question-asking is tightly coupled to domain-specific reasoning skills (propositional deduction vs. state-space planning) and that improving Logic-Q performance requires Logic-Q-specific training data. This has direct implications for whether a general-purpose question-asking module can be trained independently of underlying reasoning modules, or whether question-asking must be integrated with domain-specific reasoning engines. The paper's difficulty axes provide a natural framework for designing the transfer experiment: transfer should be strongest between domains with similar d, |X|, and |C| distributions (Table 1), even if the surface forms differ.

Practical Applications and Downstream Use Cases

Automated data validation and cleaning in structured reasoning pipelines. Organizations that process large volumes of structured reasoning tasks — math word problems for educational technology, planning specifications for logistics, logical constraint sets for software verification — routinely encounter underspecified inputs where users omit critical parameters. The QuestBench evaluation framework can be adapted as a quality assurance filter: given an incoming task, a model trained or prompted on the QuestBench format can detect whether the task is underspecified (using the detection methodology from Section 5.4), identify the sufficient variable if it is (using the question-asking methodology from Section 5.1), and flag the task for human review with a specific clarifying question rather than silently producing an incorrect answer. The paper's GSM-Q results suggest this is already viable for math domains, where models achieve over 80% question-asking accuracy and can reliably identify which variable is missing. For a tutoring platform processing 100,000 student-submitted word problems daily, automatically flagging the ~5-15% that are underspecified (extrapolating from the fraction of GSM-Plus problems that became underspecified in QuestBench's construction) and generating specific clarifying questions would reduce human review burden substantially while preventing incorrect automated feedback. The Logic-Q results (under 50% accuracy) indicate this is not yet viable for logic domains, but the CSP formalism provides a path to improvement through fine-tuning on synthetically-generated underspecified logic problems.

Uncertainty-aware planning in LLM-based robotics and agents. The catastrophic Planning-Q underspecification detection failure (Table 7, F1 0-46%, "Not sure" response rates 0.7-4.6%) is a red flag for any deployment where an LLM controls actions in a partially observable environment. A robotics system using an LLM planner that receives partial state information — e.g., a household robot that can see some but not all objects, or a warehouse robot with occluded inventory — will currently produce a confident plan based on incomplete observations rather than asking for clarifying sensor readings or human input. The practical implication is that any such system must include an explicit uncertainty quantification layer that runs before the LLM planner: before passing the partial state to the LLM, run the CSP analysis pipeline (or a learned approximation thereof) to detect whether the state is 1-sufficient for the goal, and if not, proactively query the missing information through additional sensing or human clarification. The paper's Planning-Q results provide the diagnostic (models will not do this on their own) and the BFS baselines (Table 2, depth 10 achieves 93.9% on Planning-Q) demonstrate that algorithmic CSP analysis can solve the detection problem even when LLMs cannot. A practical integration would use a lightweight CSP solver or fine-tuned classifier for the detection step, then use the LLM only for plan generation once information is complete — keeping the LLM in its demonstrated area of competence (well-specified planning, where Table 8 shows 53-70% accuracy for Planning-Q) while shoring up its demonstrated area of incompetence (underspecification detection and question selection).

Interactive tutoring and educational question-answering with Socratic scaffolding. QuestBench's formalization of 1-sufficient CSPs maps naturally onto a Socratic tutoring interaction pattern: the student presents a partially-described problem, the tutor identifies the missing information, and the tutor asks a targeted question that guides the student to supply the missing variable. The GSM-Q domain directly instantiates this: a student describes a math problem but omits a necessary number; the system asks "What is the value of [variable]?" rather than solving a different problem or guessing. The paper's GSM-Q results (over 80% accuracy, with GPT-4o at 86.81% ZS on the representative subset and 84.05% on the full 23,642-problem dataset per Footnote 9) suggest this is deployable today for grade-school math. A tutoring system that routes student queries through a QuestBench-style sufficiency check before attempting to solve would avoid the common failure mode of LLM tutors silently solving a different problem than the student intended when the student omits a constraint. The key deployment consideration is latency: the sufficiency check requires identifying the missing variable, which the paper's results suggest takes one forward pass (the question-asking step), adding minimal overhead to the overall tutoring interaction. For domains where question-asking accuracy is lower (Logic-Q at ~30-50%), the system could fall back to explicit uncertainty expression ("I'm not sure I have enough information — can you clarify [educated guess]?") rather than attempting to solve incorrectly, which is safer than confident incorrectness even if the specific question is sometimes suboptimal.

Benchmarking and model cards for epistemic humility. The paper's underspecification detection results (Table 7) provide a concrete, quantitative measure of a model's tendency toward overconfidence under missing information — a capability that current model cards and safety evaluations do not typically measure. An organization deploying an LLM in a high-stakes domain (medical, legal, financial) could add QuestBench's detection task to their evaluation suite, measuring the F1 score for "Not sure" responses and the base rate of uncertainty expression. A model that achieves near-random F1 and near-zero uncertainty expression in Planning-Q (like GPT-4o at 1.23% F1 and 0.7% response rate) should be flagged as unsuitable for partially-observable planning tasks regardless of its general reasoning benchmark scores. The QuestBench results provide the calibration: the best current models (Gemini Flash Thinking, Claude 3.5 Sonnet) achieve moderate detection in Logic-Q (F1 58-62%) but catastrophic detection in Planning-Q (F1 0-15%), so a deployment in any domain resembling Planning-Q in state-space complexity should either use a dedicated CSP-based detection module (as described above) or explicitly warn users that the model will not ask for clarification when it should. This is a quantifiable safety property that the paper enables, and its adoption in model evaluation pipelines would shift the Overton window from "does the model solve well-specified reasoning problems?" to "does the model know when it cannot solve the problem as stated?"

🎯 Pitch

1. Executive Summary

2. Context and Motivation

The Core Problem: LLMs Cannot Identify What Information They're Missing

Conflicting or Incomplete Prior Evidence

Where Existing Approaches Fall Short

How This Paper Positions Itself

3. Technical Approach

3.1 Reader Orientation

3.2 Big-Picture Architecture (Diagram in Words)

3.3 Roadmap for the Deep Dive

3.4 Detailed, Sentence-Based Technical Breakdown

The CSP Formalization of Underspecification

Difficulty Axes of 1-Sufficient CSPs

Logic-Q Construction: From SimpleLogic to 1-Sufficient Propositional CSPs

Planning-Q Construction: From PDDL Blocks World to 1-Sufficient Planning CSPs

GSM-Q and GSME-Q Construction: From GSM-Plus to 1-Sufficient Math CSPs

Evaluation Protocol

Why the Multiple-Choice Format?

4. Key Insights and Innovations

Innovation 1: Formalizing Underspecification as a CSP Creates an Objective, Cross-Domain Evaluation Framework for Information Acquisition

Innovation 2: The Distinction Between Solving Well-Specified Problems and Identifying Missing Information Is an Empirically Demonstrated Capability Gap

Innovation 3: The Difficulty Axes for 1-Sufficient CSPs Provide a Mechanism-Independent Way to Diagnose How Models Approach Information Acquisition

Innovation 4: The Near-Random Underspecification Detection in Planning-Q Reveals a Systematic Failure of Epistemic Humility

5. Experimental Analysis

Evaluation Methodology

Main Quantitative Results

Overall Question-Asking Accuracy Across Domains

Correlation Between Problem Complexity and Accuracy

Question-Asking vs. Well-Specified Reasoning: The Filtered Evaluation

Underspecification Detection

Ablation Studies and Robustness Checks

Critical Assessment

6. Limitations and Trade-offs

1. Single Benchmark Family and Single Model Architecture

2. Difficulty Estimation Cost Is Unaccounted for in Deployment-Relevant Metrics

3. The 1-Sufficient CSP Simplification Excludes Realistic Multi-Question Dialogues

4. The 14× Larger Model Baseline for the Training-Inference Tradeoff Is Never Tested

5. The Planning-Q Underspecification Detection Failure Undermines the Practical Viability of Partial-Observability Deployments

6. The CSP Formalization Assumes a Closed World of Known Variables and Constraints

7. Implications and Future Directions

How This Work Changes the Landscape

Follow-Up Research This Work Enables

Practical Applications and Downstream Use Cases

Adjacent in domain

Rankers, Judges, and Assistants: Towards Understanding the Interplay of LLMs in Information Retrieval Evaluation

Gemini Embedding: Generalizable Embeddings from Gemini