Paper deep dive
Do LLMs Know What to Ask and When? Evaluating Multi-Turn Information Seeking
Yepeng Huang, Jiawen Zhang, Michelle Dai, Xiaorui Su, Shanghua Gao, Zi Wang, Marinka Zitnik
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 89%
Last extracted: 8/18/2026, 4:43:55 AM
Summary
This paper introduces MT-InfoSeek, an evaluation suite for assessing multi-turn information seeking in Large Language Models (LLMs). The authors formalize information seeking as solving a k-underspecified constraint satisfaction problem (CSP), where k represents the number of missing variables required to determine a target. The suite contains 5,251 problems across mathematics, logic, biology, medicine, and general knowledge. The study evaluates models on their ability to predict the degree of underspecification, identify minimal sufficient sets of variables, and sequentially query information. Results indicate that models often underestimate the amount of missing information, fail to identify minimal query sets, and stop prematurely, demonstrating that information-seeking capability is distinct from answer generation ability.
Entities (16)
Relation Signals (16)
MT-InfoSeek → basedon → k-underspecified constraint satisfaction problem
confidence 95% · We formalize multi-turn information seeking as solving a k-underspecified constraint satisfaction problem... We instantiate the formulation in MT-InfoSeek
MT-InfoSeek → evaluates → multi-turn information seeking
confidence 95% · We instantiate the formulation in MT-InfoSeek... We evaluate models along three axes: what they ask, when they ask it, and how the acquired information affects the final answer.
MT-InfoSeek → containsdomains → Logic
confidence 90% · MT-InfoSeek, a controlled evaluation suite... spanning mathematics, logic, biology, medicine, and general knowledge.
MT-InfoSeek → containsdomains → Biology
confidence 90% · MT-InfoSeek, a controlled evaluation suite... spanning mathematics, logic, biology, medicine, and general knowledge.
MT-InfoSeek → containsdomains → Medicine
confidence 90% · MT-InfoSeek, a controlled evaluation suite... spanning mathematics, logic, biology, medicine, and general knowledge.
MT-InfoSeek → containsdomains → general knowledge
confidence 90% · MT-InfoSeek, a controlled evaluation suite... spanning mathematics, logic, biology, medicine, and general knowledge.
MT-InfoSeek → containsdomains → Mathematics
confidence 90% · MT-InfoSeek, a controlled evaluation suite... spanning mathematics, logic, biology, medicine, and general knowledge.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:When a user question is underspecified, a capable model should recognize that its context is insufficient, identify the missing information, ask for it, and respond only once that information determines a unique answer. We formalize multi-turn information seeking as solving a k-underspecified constraint satisfaction problem, where k is the number of variables jointly required to determine the target and therefore measures the degree of missing information. We instantiate the formulation in MT-InfoSeek, a controlled evaluation suite of 5,251 problems and 9,006 task instances spanning mathematics, logic, biology, medicine, and general knowledge. We evaluate models along three axes: what they ask, when they ask it, and how the acquired information affects the final answer. Performance degrades across models and domains as underspecification increases. Models recognize that additional information is needed but underestimate how much, and in logical problems at k = 2 they under-predict the degree of missing information about four times as often as they over-predict it. They also fail to identify a minimal sufficient set of queries, improve only marginally when given the true k, and often stop before acquiring sufficient information. In tasks with ordered dependencies, an incorrect query order reduces final accuracy even when the model eventually acquires all necessary information. We measure information seeking directly through final sufficiency, which records whether the acquired information determines the target independent of answer generation. This separation shows differences between models that final accuracy alone does not capture, and indicates that the ability to seek information over multiple turns is distinct from the ability to generate answers and is not measured by current LLM evaluations.
Tags
Links
- Source: https://arxiv.org/abs/2608.14808v1
- Canonical: https://arxiv.org/abs/2608.14808v1
Trouble viewing inline? Open PDF directly →
Full Text
220,737 characters extracted from source content.
Expand or collapse full text
Do LLMs Know What to Ask and When? Evaluating Multi-Turn Information Seeking Yepeng Huang†, Jiawen Zhang†,11footnotemark: 1 Michelle Dai† Xiaorui Su† Shanghua Gao† Zi Wang†,‡ Marinka Zitnik† †Harvard University ‡Google DeepMind Code Project page Dataset Thanks: Equal contribution. Abstract When a user question is underspecified, a capable model should recognize that its context is insufficient, identify the missing information, ask for it, and respond only once that information determines a unique answer. We formalize multi-turn information seeking as solving a k-underspecified constraint satisfaction problem, where k is the number of variables jointly required to determine the target and therefore measures the degree of missing information. We instantiate the formulation in MT-InfoSeek, a controlled evaluation suite of 5,251 problems and 9,006 task instances spanning mathematics, logic, biology, medicine, and general knowledge. We evaluate models along three axes: what they ask, when they ask it, and how the acquired information affects the final answer. Performance degrades across models and domains as underspecification increases. Models recognize that additional information is needed but underestimate how much, and in logical problems at k=2k=2 they under-predict the degree of missing information about four times as often as they over-predict it. They also fail to identify a minimal sufficient set of queries, improve only marginally when given the true k, and often stop before acquiring sufficient information. In tasks with ordered dependencies, an incorrect query order reduces final accuracy even when the model eventually acquires all necessary information. We measure information seeking directly through final sufficiency, which records whether the acquired information determines the target independent of answer generation. This separation shows differences between models that final accuracy alone does not capture, and indicates that the ability to seek information over multiple turns is distinct from the ability to generate answers and is not measured by current LLM evaluations. 1 Introduction Large language models (LLMs) often operate under incomplete information in multi-turn interactions, because a user task may be underspecified 11 1 We study underspecification, not ambiguity. [15] draws the distinction, and Appendix B.1 discusses it further.. A capable model should recognize that its context is insufficient, identify and acquire the missing information, and respond only once that information determines a unique answer [1, 2]. Interactive settings depend on this capability, but direct and systematic evaluation remains difficult. Final task success does not indicate whether a model acquired the necessary information. Existing multi-turn benchmarks measure task success, dialogue quality, or user-facing outcomes, without specifying which information the model should request or whether it stopped only after the target became identifiable [17, 10, 12, 40]. Model priors and the ability to generate answers therefore confound the evaluation. In MediQ [17], for example, a 30B model answers correctly in roughly 60–70% of cases from the initial incomplete information alone (Appendix B.2), so final accuracy overstates the ability to seek information. Simulated users and free-form responses make query-level evaluation ambiguous, because a failure may follow from a wrong question, an uninformative response, or a response that does not map onto task variables. Figure 1: Overview of the MT-InfoSeek evaluation framework. (a) Information-seeking interaction: the model queries an oracle over multiple turns, acquires the missing information, and identifies a hidden target. (b) Evaluation protocols: we evaluate three abilities, predicting the degree of underspecification k, identifying a minimal sufficient set of variables, and solving the task through sequential interaction. (c) Task construction: each problem specifies constraints, an observed assignment, a target variable, and its minimal sufficient sets, and induces task instances that share this information and differ in the hidden target value. One example problem is shown for each domain. Representing an underspecified task as a constraint satisfaction problem (CSP) removes these sources of ambiguity, because the constraints determine which variables the model needs before it can answer, and each question the model asks either names one of those variables or does not. QuestBench formalizes underspecified reasoning problems as CSPs and provides the ground-truth missing variable that a model should query [15]. It covers the special case where a single missing variable is sufficient to determine the answer, so one question ends the interaction. Multi-turn information seeking differs in structure, because several variables may be jointly necessary. The model queries one variable per turn, receives its value, and updates the set of assignments that remain feasible, so it must choose a variable at every turn and judge when the acquired information is sufficient to stop. Evaluating this requires representing joint sufficiency and tracking how each queried value changes the feasible space across turns. Neither single-turn query selection nor final accuracy captures these dimensions. Present work. We formalize multi-turn information seeking as solving a k-underspecified CSP, where k variables are jointly required to determine the target variable. The formulation provides ground truth for which variables the model needs, allows controlled variation in the degree of underspecification k, and defines when the model should stop asking and answer. We instantiate the formulation in MT-InfoSeek, an evaluation suite spanning mathematics, logic, biology, medicine, and general knowledge, with 5,251 problems and 9,006 task instances (Fig. 1). Each problem induces a family of task instances that share the same initial information and differ in the target value, so a model cannot succeed by guessing the most likely target. We study three components of multi-turn information seeking, which variables the model queries, when it stops, and how the acquired information affects the final answer. Models underestimate the degree of underspecification, perform worse as the number of missing variables grows, and stop before they acquire sufficient information. A wrong first query does not determine the outcome, since models that continue to search for target-relevant variables reach sufficiency at close to the rate of models that query correctly on the first turn, and the number of turns predicts success more strongly as k grows. In tasks with ordered dependencies, an incorrect query order lowers final accuracy even when the model acquires all necessary information. Question quality alone does not account for success either, because models given the same completed interaction can still differ in whether they correctly answer. Separating information seeking from answer generation therefore shows differences between models that final accuracy alone does not capture. We make the following contributions: • A formalization of multi-turn information seeking as solving k-underspecified CSPs, with ground truth for the variables the model needs and for when it has enough of them. • MT-InfoSeek, an evaluation suite spanning mathematics, logic, biology, medicine, and general knowledge. • An evaluation of closed and open-weight LLMs under this formulation, which measures information seeking through final sufficiency and separates it from final accuracy. 2 Related Work Multi-turn information seeking. Recent work studies LLMs in interactive settings, where models acquire information, respond to feedback, and adapt over successive turns. These include RL-based interaction [28, 24], collaborative environments [32], decision-oriented games [40, 6, 39], and medical dialogue [17, 10, 31]. A related line of work studies clarification under ambiguity or underspecification, including generation of clarification questions [34, 23, 38], Bayesian experimental design for question selection [12, 3], and proactive clarification in retrieval-augmented systems [16]. These studies establish settings and mechanisms for interaction, feedback, and ambiguity resolution. We treat multi-turn interaction as controlled information acquisition, where the model identifies missing variables that determine the target, queries them in as few turns as possible, and stops once the acquired information is sufficient to produce an answer. Benchmarking under incomplete information. Existing studies evaluate information seeking across clinical, mathematical, logical, and common-knowledge domains [17, 10, 12, 40, 15, 35], but they primarily measure performance through final task success, dialogue quality, or judge-mediated outcomes. QuestBench [15] is closest to our setting, since it gives ground-truth missing variables through an underspecified CSP formulation, and we extend this formulation to the multi-turn setting where the model acquires information sequentially. 13 show that LLMs perform worse when fully specified instructions are split into shards and revealed over turns. Our work is complementary. We give the model an underspecified task and test whether it identifies the missing variables, queries them over successive turns, and stops once the acquired information determines the target. Appendix Table 2 compares MT-InfoSeek with existing benchmarks in detail. 3 MT-InfoSeek Evaluation Framework We formalize multi-turn information seeking as solving an underspecified CSP (§3.1). We then define the protocols and metrics that separate information seeking from answer generation (§3.2), and construct MT-InfoSeek, an evaluation suite that instantiates the formulation in mathematics, logic, biology, medicine, and general knowledge (§3.3). 3.1 Problem Formulation We define a problem as a tuple P=⟨,,,,Y⟩P= ,D,C,A,Y , where X is a set of variables with domains D, C is a set of logical constraints over these variables, A is an observed partial assignment, and Y is the target variable. Let Ω(P) (P) denote the feasible space, the set of all full assignments consistent with both C and A. Intuitively, Ω(P) (P) contains the underlying states that remain possible given the available information (Fig. 1a). Example: 20 Questions animal-guessing game (fixed-trait view) Variables X include the target variable Y and latent traits (e.g., can_swim). Constraints C define logical relations (e.g., Y=penguin⇒can_swim=TrueY=penguin \_swim=True). Given observed assignment =can_swim=TrueA=\can\_swim= True\, the feasible space Ω(P) (P) contains all identities and traits consistent with this clue. Interaction: Each question aims to assign a value to a trait, progressively restricting Ω(P) (P) until all remaining assignments agree on Y. To formalize this interactive process, we write (P)=∖(dom()∪Y)U(P)=X (dom(A)∪\Y\) for the set of queryable variables, those that are unassigned and are not the target, and define the following properties. • Known Target & Underspecification: Y is known under A if all feasible assignments in Ω(P) (P) share the same value for Y. If multiple values remain possible (e.g., knowing only can_swim leaves both Y=penguinY=penguin and Y=dolphinY=dolphin feasible), the problem is underspecified. • Sufficient Set: A subset of variables S⊆(P)S (P) is sufficient if, for every valid assignment s to S, the target variable Y becomes known under the updated assignment ∪S=sA∪\S=s\. • Minimal k-Sufficient Set (k-MSS): A set S⊆(P)S (P) is a k-MSS if it is sufficient, has a size of k, and no strictly smaller subset of (P)U(P) is sufficient. This value k defines the problem-level degree of underspecification. We distinguish a problem from its induced task instances Ty=(P,y)T_y=(P,y), where y∈Y(ω):ω∈Ω(P)y∈\Y(ω):ω∈ (P)\ is the hidden target value and Y(ω)Y(ω) is the value of Y under a full assignment ω. The task instances induced by a single problem P form its task family, and they share C and A and differ only in y. The task-level degree of underspecification, the minimum number of variables needed to determine a specific y, can be strictly smaller than the problem-level degree k. The asymmetry follows because k is the worst-case number of queries needed across all feasible target values, while a specific y can be separated from the rest of the feasible space in fewer than k queries. Example of task-level asymmetry Suppose the observed assignment =can_swim=TrueA=\can\_swim=True\ leaves four feasible target values, Y∈shark,dolphin,penguin,turtleY∈\shark,dolphin,penguin,turtle\. Distinguishing every target value in this set requires a 3-MSS, for example S=has_gills,lays_eggs,has_feathersS=\has\_gills,lays\_eggs,has\_feathers\, so the problem-level degree is k=3k=3. If the task is TsharkT_shark, then querying has_gills alone is sufficient, since the answer True eliminates the other three candidates, and the task-level degree is 11. Solving TpenguinT_penguin requires all three variables to exclude the fish, the mammal, and the reptile, so its task-level degree is 33. Prior single-turn studies represent the special case of k=1k=1 [15]. For k>1k>1, solving a task instance TyT_y requires making a series of decisions, which are studied here. At each turn t, the model queries a variable Xt∈(P)X_t (P). The oracle returns its value xtx_t, and the partial assignment becomes t+1=t∪Xt=xtA_t+1=A_t∪\X_t=x_t\, starting from 1=A_1=A. The interaction continues until the model commits to an answer (Appendix C.1). 3.2 Multi-Turn Evaluation Protocol We define three evaluations for each problem P and its task family, which separate the components of information seeking that a single interaction would otherwise combine. The first two operate at the problem level. They present the model with P alone and ask it to report how much information is missing and which variables would supply it, so a failure at this stage reflects the model’s assessment of the problem and not its conduct of a multi-turn interaction. The third operates at the task level. The model receives P, queries one variable per turn, observes the returned value, and decides at every turn whether to query again or to answer, so its performance depends on the sequence of queries it selects and on when it stops. • Degree of underspecification prediction (k-prediction): Given problem P, the model predicts the degree of underspecification k k. This setting tests whether the model recognizes how much information is missing. • Missing variables identification (k-MSS identification): Given problem P, and in one condition the true k, the model selects a minimal sufficient set from (P)U(P). This setting tests whether the model plans a minimal query strategy without executing it. • Sequential task-solving (multi-turn interaction): Given a task instance Ty=(P,y)T_y=(P,y), the model observes only P. At each turn, it queries a variable Xt∈(P)X_t (P) from an oracle or predicts y y. This setting tests the full interaction, where the model acquires information, updates its state, and answers once it judges the information sufficient. To control for priors over targets, we evaluate models on the complete task family of each problem P. Because every instance in a family shares the same observed assignment A and differs only in the hidden target y, a model cannot succeed by guessing the most likely target and must instead narrow the feasible space through its queries. Appendix C.2 provides further details on our multi-turn evaluation protocol. Metrics. We use different metrics for each setting, with formal definitions in Appendix C.3. For k-prediction, we report accuracy together with the rates of overestimation and underestimation, the fraction of problems where k^>k k>k and where k^<k k<k. For MSS identification, we measure exact-set accuracy and Jaccard similarity against the ground truth MSS. For sequential task solving, we report final accuracy, whether y^=y y=y, and final sufficiency, whether the acquired information determines y uniquely. Final sufficiency differs from exact-set accuracy in MSS identification, because it is measured after a multi-turn interaction and reflects the variables the model actually queried. We also report behavioral metrics, including the total number of turns and the coverage, correctness, and ordering of queries. From reasoning traces, we compute the MSS relative mention rate, the fraction of the variables the model considers querying that belong to the MSS, and awareness of underspecification (Appendix G.1.1). 3.3 Datasets MT-InfoSeek instantiates multi-turn information seeking in mathematics, logic, biology, medicine, and general knowledge. Four domains are structured, in the sense that the queryable variables (P)U(P) are predefined and finite and the model selects one of them at each turn. In these domains, we generate k-underspecified problems for k∈1,2,3,4k∈\1,2,3,4\ where feasible, by masking variables from fully specified states and verifying that each masked set is a valid k-MSS. We then evaluate models on the task instances TyT_y that each problem induces. The fifth domain, 20Q, is unstructured, since the model composes its own questions instead of selecting from a predefined (P)U(P), and each question induces its own partition of the candidate set. The problem-level degree k and the exact MSS are therefore not defined in advance, and 20Q tests information seeking under open-ended exploration. Appendix D reports dataset statistics and construction details. Logic-Q-MT. We extend the logical CSPs from 15 from single missing-variable settings to multi-turn interactions. Starting from rule-based reasoning environments, we recursively construct k-MSSs, requiring the model to sequentially identify and query the missing facts necessary to prove or disprove a target proposition. This domain explicitly evaluates information seeking and sufficiency judgment under strict formal logic. Details are provided in Appendix D.1. GSME-Q-MT and GSME-Q-MT-Ext. GSME-Q contains an equation-based version of the grade-school math problems with human-annotated missing conditions required to compute an answer [15]. Because the original dataset masks only a single variable (k=1k=1), we extend it to a multi-turn setting (GSME-Q-MT) by systematically masking multiple quantities. However, we found that GSME-Q-MT is nearly saturated; modern LLMs solve it reliably due to shallow constraints and weakly entangled variables. Consequently, we introduce GSME-Q-MT-Ext, a rigorously enriched variant featuring deeper dependency structures, larger variable sets, and strictly validated k-MSSs. This extension provides a more diagnostic testbed for evaluating dependency tracking and step-wise mathematical information acquisition. Details are provided in Appendix D.2. GeneReg-MT. We construct tasks from Boolean models of gene regulation. The variables X are gene expression states, the constraints C are Boolean update rules, and the target Y is either a steady state or the value of a marker gene at convergence. We refer to the two settings as steady state identification and marker identification. We mask initial gene expression values that determine Y, so the model must acquire the genes that fix the outcome under cyclic regulatory dependencies. Appendix D.3 gives the construction details. Figure 2: Example ClinGuide-MT diagnostic pathway for pelvic pain [7, 5, 30]. ClinGuide-MT. Clinical reasoning proceeds by acquiring evidence in sequence before a diagnosis or management decision [14, 18, 29]. We construct tasks from diagnostic decision trees in clinical guidelines and textbooks (Fig. 2). Internal nodes are the clinical variables X, including symptoms, risk factors, and test results, and leaf nodes are the target outcome Y, a diagnosis, treatment, triage decision, or follow-up recommendation. We create k-underspecified problems by withholding the values of the last k variables on a diagnostic pathway from the root to a leaf. Because a pathway encodes conditional dependencies, where an earlier finding determines which later variables are relevant, ClinGuide-MT tests both which variables the model queries and in which order. Appendix D.4 gives the construction details. 20Q. We use the 20 Questions game as an open-domain information-seeking setting. The hidden target Y is sampled from a finite candidate set, and the model must deduce it by generating natural language yes-or-no questions. Each question partitions the feasible space Ω(P) (P) into subsets (yes, no, or pass, where pass indicates ambiguity). Unlike the structured domains above, 20Q does not provide a predefined, finite (P)U(P). Instead, the model dynamically generates constraints over the candidate set. 20Q thus serves as an open-ended extension of our framework: claims involving k and MSS identification are grounded in the four structured domains, while 20Q tests free-form question generation and integration of natural-language evidence. We evaluate models on two subsets: Common (animals, places, food) and Thing (general objects). Details on 20Q are provided in Appendix D.5. 4 Results We organize our experiments around three research questions. RQ1: Which variables to query? We evaluate whether models recognize the missing information and identify the variables that determine the target, through k-prediction, MSS identification, and sequential task solving. Our primary metric is final sufficiency, which records whether the acquired information determines the target, independent of the answer the model gives. The separation matters because models answer Logic-Q-MT correctly when we provide the values of all MSS variables (Table 21), so failures under underspecification follow from insufficient information seeking and not from an inability to reason to the answer. RQ2: In which order to query them? We evaluate whether models acquire information in a valid order when the task imposes dependencies among variables. ClinGuide-MT provides this structure, since an earlier finding determines which variables are relevant next. RQ3: How does the model use the acquired information? We analyze whether the acquired information improves target identification. We report final accuracy together with the reduction in uncertainty at each turn and the ambiguity of the questions, which separates the informativeness of a question from the use the model makes of the answer. Complete benchmarking results are in Appendix F, with additional analyses in Appendix G. Models. We evaluate closed and open-weight LLMs, including GPT-5, GPT-5-mini, Gemini-3-Flash, Qwen3-4B-Thinking, Qwen3-30B-A3B-Thinking-FP8, and gpt-oss-20B. Compute constraints limit Gemini-3.1-Pro, gpt-oss-120B, Qwen3-Next-80B-A3B-Thinking-FP8, and the Qwen3.5 family to a subset of settings; the corresponding appendix tables list the models evaluated in each setting. General experimental setup. Unless otherwise specified, models are not given an explicit turn budget, but interactions are capped at 10 turns for consistency; this cap does not significantly affect final sufficiency (Appendix Fig. 23). 20Q sets a 20-turn budget per the game design. Oracles vary by dataset: we use an oracle algorithm for GSME-Q-MT, Logic-Q-MT, and GeneReg-MT, and an LLM-based oracle for ClinGuide-MT and 20 Questions (Appendix C.4). Qualitative conclusions hold across oracle response policies (Appendix C.5), and the LLM-based oracles are validated for self-consistency, cross-oracle agreement, and agreement with human annotation (Appendix C.6). In Logic-Q-MT, alternative MSSs are forbidden as queries to ensure fair comparison, and our conclusions are insensitive to the designated MSS (Appendix G.1.6). Implementation details and dataset-specific prompts are provided in Appendix E. Prompts were fixed before the model comparison and shared across models (Appendix G.1.4). Figure 3: (a) Accuracy of predicting the true k. Light gray lines denote individual models and the black line their mean. (b) Rate at which models predict a value smaller (red) or larger (blue) than the true k; dots are individual models. Takeaway 1 (RQ1) Models detect that their context is insufficient to determine the target, but they underestimate how many additional variables they need before the target becomes identifiable. We first test whether LLMs can quantify missing information via multiple-choice k-prediction, selecting from 0,1,2,3,4,not sure\0,1,2,3,4,not sure\, in Logic-Q-MT. We found that models rarely classify underspecified problems as fully specified (only predicting 0.6±0.8%0.6±0.8\% of problems as k=0k=0), but they struggle to calibrate how much information is missing (Fig. 3). Accuracy drops sharply as k increases, falling below 0.50.5 for k≥2k≥ 2 (per-model results in Appendix Table 20). Errors are consistently biased toward underestimation: for k=2k=2, where choices are balanced above and below the true value, models predict a smaller k more than 4×4× as often as a larger one on average. Takeaway 2 (RQ1) Detecting that information is missing does not imply identifying which information. Even when given the degree of underspecification k, models often fail to select a minimal set of variables that determines the target. Figure 4: Models predict the MSS of each problem in Logic-Q-MT, either (a) without knowing k or (b) given the true k and asked to select exactly k variables. We report exact-set accuracy against the true MSS. Gray lines denote individual models, black lines the mean, and dashed lines a uniform-random baseline. We next ask whether LLMs know what missing variables to ask for to solve underspecified problems. When models freely choose up to four variables (k not provided), their exact-set accuracy is low and drops sharply as k increases: no model exceeds 0.40.4 accuracy at k=2k=2 or 0.20.2 at k=3k=3 (Fig. 4a). Providing the true k improves performance, but only modestly; both exact-set accuracy and Jaccard similarity remain low for k≥2k≥2 (Fig. 4b). Thus, estimating the amount of missing information is helpful but insufficient: the harder challenge is identifying which variables form the target-relevant MSS. Jaccard similarity and recall trends are consistent (Appendix Fig. 24; per-model results in Appendix Table 21). Takeaway 3 (RQ1) Under a fixed query budget, models often acquire more of the required information when queries are spread across turns instead of being issued together in one turn. We next study how interaction budgets affect final sufficiency. We prompt LLMs with different budgets of turns (Appendix E.1) and number of questions allowed per turn, and measure the final sufficiency. In Logic-Q-MT and GeneReg-MT, final sufficiency generally increases as more turns are allowed, and, under the same total query budget, allocating queries across more turns often outperforms allowing more queries per turn (Appendix Figs. 25,26). Appendix Fig. 27 traces the proportion of sufficient interactions turn by turn, with the separation between models widening as k increases. This pattern shows that the benefit of interaction is not captured by the total number of queries alone, and how queries are distributed across turns also matters. However, forced multi-turn execution can introduce additional failures when models underestimate k. In GSME-Q-MT, constraining models to query only one variable per turn often causes them to stop too early and directly guess the final answer, thereby degrading performance (Table 16, Appendix Fig. 39). Figure 5: Correlation between per-model behavioral features and final sufficiency in Logic-Q-MT. Each cell reports the Pearson correlation across models between final sufficiency and a behavioral feature, computed separately for each k. Takeaway 4 (RQ1) Success on highly underspecified problems depends less on the first query and more on sustained information acquisition across turns. Early-turn query correctness predicts final sufficiency at small k, and at larger k, stronger models keep identifying useful variables over longer interactions. The preceding results motivate a closer look at which model behaviors might explain final sufficiency. For each k, we compute model-level Pearson correlations between final sufficiency and three behavioral features in Logic-Q-MT: early-turn (turns 1-3) query correctness, late-turn (turns 4+) query correctness, and number of turns. Early-turn correctness is strongly correlated with final sufficiency when underspecification is mild (r=0.60r=0.60 at k=1k=1), but its correlation vanishes at k=3k=3 (r=−0.05r=-0.05; Fig. 5, Appendix Fig. 28). On the other hand, late-turn correctness remains consistently correlated with success (r=0.46r=0.46–0.480.48), and the correlation with the number of turns increases with k (r=0.19→0.66r=0.19→0.66). A similar turn-count trend appears in GeneReg-MT, reaching r=0.77r=0.77 on steady state identification (Appendix Fig. 29) and 0.970.97 on marker identification (Appendix Fig. 30) at k=4k=4. Takeaway 5 (RQ1) A first query that misses the minimal sufficient set is often recoverable. Interactions in which the model keeps searching for target-relevant variables reach sufficiency at close to the rate of interactions whose first query is correct. Building on Takeaway 4, we ask whether missing an MSS variable on the first turn necessarily prevents a interaction from reaching sufficiency. We focus on tasks with k≥2k≥2 and compare two groups of interactions: those where the first query targets an MSS variable, and those where the first query does not target an MSS variable but the second query does. Figure 6: Final sufficiency between interactions where the first query targets an MSS variable and interactions where the first query misses an MSS variable but the second query targets one. Gray lines denote individual models and the black line their mean. Stars mark models for which this comparison passes a one-sided Miettinen–Nurminen non-inferiority test with a 10 percentage-point margin (p<0.05p<0.05). In Logic-Q-MT, the latter group achieves final sufficiency close to the first-turn-hit group for both k=2k=2 and k=3k=3 (Fig. 6; per-model results in Appendix Fig. 33). The gap is small for most models: it is within 5 percentage points for 12 out of 14 models, and within 10 percentage points for all models (Appendix Fig. 36). Using a one-sided Miettinen–Nurminen non-inferiority test with a 10 percentage-point margin, we find statistically supported near-parity for 8/14 models at k=2k=2 and 7/14 models at k=3k=3. The pattern is qualitatively similar but weaker in GeneReg-MT, where recovery cases are less frequent (per-model results in Appendix Figs. 34, 35; sensitivity in Appendix Fig. 37). These results show that early query misses are not necessarily fatal: what matters is whether the model continues to search and identify target-relevant missing variables. First-turn mentions of MSS variables predict later recovery. To probe why some first-turn misses are recoverable, we analyze the model’s visible first-turn reasoning traces. In Logic-Q-MT, the first-turn MSS relative mention rate is positively associated with both second-turn hit after a first-turn miss (log odds ratio =0.365=0.365, p<p<1e-4) and final sufficiency (log odds ratio =0.528=0.528, p<p<1e-4), even after controlling for CoT length, first-turn query mention, degree of underspecification, model type, and problem-difficulty factors (Appendix Fig. 18). By contrast, awareness of underspecification has near-zero adjusted association. These results suggest that some recovery cases are preceded by specific partial recognition of the relevant missing variables, even when the model does not select those variables as its first query. MSS relative mention rate remains positive in steady-state and marker identification subsets in GeneReg-MT, though the effects are noisier (Appendix Fig. 20). Takeaway 6 (RQ2) In order-dependent tasks, querying the right variables is not enough if the model queries them in the wrong order. Clinical diagnostic pathways impose conditional dependencies, and violating them lowers final accuracy even when the model eventually acquires every necessary variable. In ClinGuide-MT, diagnostic pathways impose ordered dependencies among clinical variables, where earlier findings determine which downstream questions are relevant and how their answers should be interpreted. For example, as illustrated in Fig. 2, whether a patient has acute or chronic pelvic pain changes which examination should be performed next. This setting allows us to evaluate not only whether models identify the underspecified information, but also whether they acquire it in a dependency-consistent order. We find that following the correct query order consistently improves final accuracy both in MSS fully covered and partially covered interactions (Fig. 7). This effect is more pronounced in more difficult settings with larger k and more distractors. We further quantify the effect of query coverage, order correctness, and query correctness to final accuracy using regression analysis, (Appendix Fig. 41 and Appendix G.3). Query coverage remains the strongest and most stable positive predictor of final accuracy, while order correctness is generally the second strongest positive predictor. Query correctness (i.e., avoiding off-branch or irrelevant queries) provides additional benefit and becomes more salient in more difficult settings. These effects persist even in a deliberately favorable open-book setting that provides all source diagnostic algorithms verbatim, largely reducing the task to locating and following the correct pathway; accuracy rises substantially yet remains unsaturated (Appendix G.3.1). Figure 7: ClinGuide-MT final accuracy stratified by MSS coverage and query order for k∈3,4k∈\3,4\ with 1010 distractor variables. Takeaway 7 (RQ3) Informative queries are necessary but not sufficient for identifying the target. Models whose queries carry similar expected information gain differ substantially in final accuracy, so success also depends on how the model integrates the acquired evidence into its belief over the remaining candidates. We measure question informativeness using the average normalized expected information gain (nEIG) of a model’s questions (Appendix D.5.5); nEIG matches blinded human preferences in a forced-choice study (76.5% of 200 pairs, 86.5% at high annotator confidence; Appendix D.5.7). As shown in Fig. 8(a), higher-gain questions generally correlate with higher final target-identification accuracy, suggesting that effective information seeking is important for 20Q. However, models with similar question informativeness can still differ substantially in final accuracy, indicating that success also depends on how well they use the collected answers. To isolate this effect, Fig. 8(b) performs trace transfer: given the same completed QA dialogue, we replace the original guesser with different answer models and ask each to infer the target. Stronger answer models identify the target more reliably from identical traces, showing that some failures come not from asking uninformative questions, but from failing to integrate the acquired evidence. (a) Acc. (↑ ) vs. question informativeness (↑ ). (b) Final target identification from the same QA dialogue. Figure 8: Interaction-level analysis on 20Q. (a) Final accuracy and question informativeness, measured by normalized expected information gain. r denotes Pearson correlation and ρ denotes Spearman rank correlation. (b) Target identification accuracy across answer models given the same completed QA dialogue. Takeaway 8 (RQ3) Models narrow the candidate space well and separate the remainder poorly. Early queries eliminate most of the feasible space, and later queries often fail to distinguish closely related target values that remain. We measure remaining entropy as the uncertainty of the posterior distribution over candidate targets after each turn. As shown in Fig. 9(a), remaining entropy decreases across turns for nearly all models and settings, indicating that the interaction generally provides useful information for narrowing the candidate set. However, the curves often flatten in later turns, suggesting that models become less effective at further reducing uncertainty once the candidate space has already been narrowed. Stronger models maintain lower entropy throughout the interaction, reflecting more efficient evidence acquisition and use, whereas weaker models plateau earlier and retain more residual uncertainty. These results suggest that the challenge is not only in making initial progress, but also in continuing to distinguish among the remaining plausible targets. Additional turn-level results, including both examiners, are provided in Appendix G.4.1. (a) Remaining entropy across turns. (b) Probability mass of candidates consistent with pass. Figure 9: Turn-level analysis on 20Q under the examiner GPT-5-mini. Takeaway 9 (RQ3) A partially informative answer is not a failed turn. Stronger models extract evidence from responses that do not separate the candidates and use it in later turns to narrow the remaining target values. Fig. 9(b) reports pass support mass at each turn, i.e., how much of the model’s current candidate belief falls on targets for which the question cannot be clearly answered with yes or no (Appendix D.5.5). Higher pass mass means the question less cleanly partitions the remaining candidates under the binary-answer protocol. For most models, pass mass increases over the interaction, suggesting that later questions tend to become more borderline or partially applicable as the remaining candidates become harder to distinguish. However, high pass mass does not consistently imply lower final accuracy. Several stronger models remain competitive despite asking high-pass questions, suggesting that pass feedback can still provide useful partial evidence when models continue to update the search space rather than treating it as a failed query. We further analyze representative failure modes through qualitative case studies in Appendix G.4.2. 5 Discussion and Conclusion We study multi-turn information seeking under underspecification, where the model recognizes the missing information, acquires it through interaction, and uses it to determine the target. Across mathematics, logic, biology, medicine, and general knowledge, current LLMs detect underspecification but underestimate its degree, query incomplete sets of variables, and stop before the acquired information determines the target. Final accuracy alone therefore does not measure interactive competence. Evaluation should also record whether the model recognizes that its context is insufficient, which variables it needs, and whether it acquires them over successive turns. MT-InfoSeek supports this evaluation by measuring final sufficiency, which separates the ability to answer from the ability to acquire the information that determines the answer. Limitations and future work. Future work should extend the setting to richer user models, with ambiguous, noisy, changing, or inconsistent responses [21], to probabilistic formulations of uncertainty, to longer conversations [20], and to forms of underspecification beyond missing variables, such as missing rules or unknown constraints [6, 33]. We treat every query as equally expensive, while acquisition in practice differs in effort, latency, invasiveness, and risk. Unequal costs would turn query selection into a decision under a budget. An LLM serves as the oracle in ClinGuide-MT and 20Q. Consistency, cross-model, and human-agreement checks indicate that the oracle does not account for the failures we report (Appendix C.6), and human-audited protocols remain a useful extension. Normalized expected information gain measures the expected reduction in uncertainty over a surrogate candidate pool, which we validate against blinded human judgments (Appendix D.5.7). It does not measure question informativeness in a broader sense. ClinGuide-MT uses pathways from published guidelines to evaluate information seeking, and it does not establish clinical readiness. Analyses of reasoning traces and internal states may further clarify when a model tracks the missing information and when apparent recovery reflects shallow exploration [27]. Acknowledgments and Disclosure of Funding We thank Alexander D’Amour, Yuchang Su, Kexin Chen, Yasha Ektafaie, Kevin Li, and Pengwei Sui for helpful discussions. Z.W. provided advisory contributions; this work was partially conducted during a prior lecturing appointment at Harvard University in a Google DeepMind capacity. Y.H., M.D., X.S., S.G., and M.Z. gratefully acknowledge the support, in part, by NSF CAREER Award 2339524, ARPA-H Biomedical Data Fabric (BDF) Toolbox Program, Amazon Faculty Research, Google Research Scholar Program, AstraZeneca Research, GlaxoSmithKline Award, Roche Alliance with Distinguished Scientists (ROADS) Program, Sanofi iDEA-iTECH Award, Boehringer Ingelheim Award, Merck Award, Optum AI Research Collaboration Award, Pfizer Research, Gates Foundation (INV-079038), Chan Zuckerberg Initiative, Collaborative Center for XDP at Massachusetts General Hospital, John and Virginia Kaneb Fellowship at Harvard Medical School, Biswas Computational Biology Initiative in partnership with the Milken Institute, and the Kempner Institute for the Study of Natural and Artificial Intelligence at Harvard University. This work was delivered as part of the AURORA project supported by the Cancer Grand Challenges partnership funded by Cancer Research UK ([CGCAI1-Mar26/100001]). Any opinions, findings, conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the funders. References [1] S. Amershi, D. Weld, M. Vorvoreanu, A. Fourney, B. Nushi, P. Collisson, J. Suh, S. Iqbal, P. N. Bennett, K. Inkpen, J. Teevan, R. Kikin-Gil, and E. Horvitz (2019) Guidelines for human-AI interaction. In Proceedings of the 2019 CHI Conference on Human Factors in Computing Systems, Glasgow Scotland Uk, p. 1–13 (en). External Links: ISBN 9781450359702, Link, Document Cited by: §1. [2] G. Bansal, J. W. Vaughan, S. Amershi, E. Horvitz, A. Fourney, H. Mozannar, V. Dibia, and D. S. Weld (2024) Challenges in human-agent communication. (arXiv:2412.10380). Note: arXiv:2412.10380 External Links: Link, Document Cited by: §1. [3] D. Choudhury, S. Williamson, A. Goliński, N. Miao, F. B. Smith, M. Kirchhof, Y. Zhang, and T. Rainforth (2026) BED-LLM: intelligent information gathering with LLMs and bayesian experimental design. In ICLR, Cited by: §2. [4] M. Couceiro and E. Lehtonen (2007) On the effect of variable identification on the essential arity of functions on finite sets. International Journal of Foundations of Computer Science 18 (5), p. 975–986. Cited by: footnote 2. [5] N. I. for Health and C. Excellence (2021) Pelvic floor dysfunction: prevention and non-surgical management. Note: NICE Guideline NG210 External Links: Link Cited by: Figure 2, Figure 2. [6] G. Grand, V. Pepe, J. B. Tenenbaum, and J. Andreas (2026) Shoot first, ask questions later? building rational agents that explore and act like people. In ICLR, Cited by: §2, §5. [7] M. C. Henderson, L. M. Tierney, and G. W. Smetana (2012) The patient history: an evidence-based approach to differential diagnosis. 2nd edition, McGraw-Hill Education / Medical, New York. External Links: ISBN 9780071624947 Cited by: §C.6, §D.4.1, Table 11, §G.3.1, Table 28, Figure 2, Figure 2. [8] Z. Hu, C. Liu, X. Feng, Y. Zhao, S. Ng, A. T. Luu, J. He, P. W. W. Koh, and B. Hooi (2024) Uncertainty of thoughts: uncertainty-aware planning enhances information seeking in LLMs. In NeurIPS, Cited by: Table 11. [9] Institute of MedicineL. Olsen, D. Aisner, and J. M. McGinnis (Eds.) (2007) The learning healthcare system: workshop summary. The National Academies Press, Washington, DC. External Links: Document, Link Cited by: §B.1. [10] S. Johri, J. Jeong, B. A. Tran, D. I. Schlessinger, S. Wongvibulsin, L. A. Barnes, H. Zhou, Z. R. Cai, E. M. Van Allen, D. Kim, et al. (2025) An evaluation framework for clinical use of large language models in patient interaction tasks. Nature medicine 31 (1), p. 77–86. Cited by: Table 2, §1, §2, §2. [11] C. Kadelka, T. Butrie, E. Hilton, J. Kinseth, A. Schmidt, and H. Serdarevic (2024) A meta-analysis of boolean network models reveals design principles of gene regulatory networks. Science advances 10 (2). Cited by: §D.3, Table 11. [12] K. Kobalczyk, N. Astorga, T. Liu, and M. van der Schaar (2025) Active task disambiguation with LLMs. In ICLR, Cited by: Table 2, §1, §2, §2. [13] P. Laban, H. Hayashi, Y. Zhou, and J. Neville (2026) LLMs get lost in multi-turn conversation. In ICLR, Cited by: Table 2, §2. [14] R. S. Ledley and L. B. Lusted (1959) Reasoning foundations of medical diagnosis: symbolic logic, probability, and value theory aid our understanding of how physicians reason. Science 130 (3366), p. 9–21 (en). External Links: ISSN 0036-8075, 1095-9203, Link, Document Cited by: §3.3. [15] B. Z. Li, B. Kim, and Z. Wang (2025) QuestBench: can LLMs ask the right question to acquire information in reasoning tasks?. In NeurIPS, Cited by: §B.1, Table 2, Definition C.3, §D.1, §D.1, Table 11, §E.1, §E.1, §E.1, §G.1.4, §1, §2, §3.1, §3.3, §3.3, footnote 1. [16] R. Li, Y. Xu, X. Jiang, Z. Yang, X. Ma, Y. Fang, J. Zhao, Y. Wang, and X. Chu (2026) GPS: graph-guided proactive information seeking in large language models. In ICLR, Cited by: §2. [17] S. S. Li, V. Balachandran, S. Feng, J. S. Ilgen, E. Pierson, P. W. Koh, and Y. Tsvetkov (2024) MediQ: question-asking LLMs and a benchmark for reliable interactive clinical reasoning. In NeurIPS, Vol. 37, p. 28858–28888. Cited by: Table 2, §C.6, §1, §2, §2. [18] N. Mehandru, N. Golchini, D. Bamman, T. Zack, M. F. Molina, and A. Alaa (2025) ER-REASON: A benchmark dataset for LLM-based clinical reasoning in the emergency room. CoRR abs/2505.22919. External Links: Link, Document, 2505.22919 Cited by: §3.3. [19] M. Mizrahi, G. Kaplan, D. Malkin, R. Dror, D. Shahaf, and G. Stanovsky (2024) State of what art? a call for multi-prompt LLM evaluation. Transactions of the Association for Computational Linguistics 12, p. 933–949. Cited by: §C.6, §G.1.4, §G.1.6. [20] S. R. Motwani, D. Nichols, C. London, P. Li, F. Pizzati, A. Blake, H. Hammoud, T. McDonald, A. Naik, A. Ivanova, et al. (2026) LongCoT: benchmarking long-horizon chain-of-thought reasoning. arXiv preprint arXiv:2604.14140. Cited by: §5. [21] B. Ni, Y. Wang, L. Wang, B. Kveton, F. Dernoncourt, Y. Xia, H. Chen, R. Luera, S. Basu, S. Mukherjee, et al. (2026) A survey on LLM-based conversational user simulation. In Proceedings of the 19th Conference of the European Chapter of the Association for Computational Linguistics (Volume 1: Long Papers), p. 4266–4301. Cited by: §5. [22] J. R. Platt (1964) Strong inference. Science 146 (3642), p. 347–353. External Links: Document Cited by: §B.1. [23] V. Pyatkin, J. D. Hwang, V. Srikumar, X. Lu, L. Jiang, Y. Choi, and C. Bhagavatula (2023) ClarifyDelphi: reinforced clarification questions with defeasibility rewards for social and moral situations. In ACL, p. 11253–11271. Cited by: §2. [24] C. Qian, Z. Liu, A. Prabhakar, J. Qiu, Z. Liu, H. Chen, S. Kokane, H. Ji, W. Yao, S. Heinecke, et al. (2025) Userrl: training interactive user-centric agent via reinforcement learning. arXiv preprint arXiv:2509.19736. Cited by: §2. [25] A. Salomaa (1964) On essential variables of functions, especially in the algebra of logic. Annales Fennici Mathematici (339), p. 1–11. Cited by: footnote 2. [26] M. Sclar, Y. Choi, Y. Tsvetkov, and A. Suhr (2024) Quantifying language models’ sensitivity to spurious features in prompt design or: how I learned to start worrying about prompt formatting. In The Twelfth International Conference on Learning Representations (ICLR), Cited by: §C.6, §G.1.4, §G.1.6. [27] G. Serapio-García, M. Safdari, C. Crepy, L. Sun, S. Fitz, P. Romero, M. Abdulhai, A. Faust, and M. Matarić (2025) A psychometric framework for evaluating and shaping personality traits in large language models. Nature Machine Intelligence, p. 1–15. Cited by: §5. [28] L. Shani, A. Rosenberg, A. Cassel, O. Lang, D. Calandriello, A. Zipori, H. Noga, O. Keller, B. Piot, I. Szpektor, A. Hassidim, Y. Matias, and R. Munos (2024) Multi-turn reinforcement learning from preference human feedback. In NeurIPS, Cited by: §2. [29] A. Sikora, L. A. Celi, and R. E. Abdulnour (2026) Can AI say “I don’t know”?. New England Journal of Medicine 394 (19), p. 1873–1875. External Links: Document, Link, https://w.nejm.org/doi/pdf/10.1056/NEJMp2517624 Cited by: §3.3. [30] S. D.C. Stern, A. S. Cifu, and D. Altkorn (2014) Symptom to diagnosis an evidence based guide. 3rd edition, McGraw-Hill Education / Medical, New York. External Links: ISBN 9780071803441 Cited by: Table 11, Figure 2, Figure 2. [31] Z. Wang, H. Li, D. Huang, H. Kim, C. Shin, and A. M. Rahmani (2025) Healthq: unveiling questioning capabilities of LLM chains in healthcare conversations. Smart Health 36, p. 100570. Cited by: §2. [32] S. Wu, M. Galley, B. Peng, H. Cheng, G. Li, Y. Dou, W. Cai, J. Zou, J. Leskovec, and J. Gao (2025) CollabLLM: from passive responders to active collaborators. In ICML, p. 67260–67283. Cited by: §2. [33] J. Yang, K. Lieret, J. Ma, P. Thakkar, D. Pedchenko, S. Sootla, E. McMilin, P. Yin, R. Hou, G. Synnaeve, D. Yang, and O. Press (2026) ProgramBench: can language models rebuild programs from scratch?. External Links: 2605.03546, Link Cited by: §5. [34] L. Yu, H. Chen, S. I. Wang, T. Lei, and Y. Artzi (2020) Interactive classification by asking informative questions. In ACL, p. 2664–2680. Cited by: §2. [35] B. Yue, Z. Zhu, Y. Zhang, J. Feng, H. Yang, and M. Wang (2026) Interactive benchmarks. arXiv preprint arXiv:2603.04737. Cited by: Table 2, §2. [36] H. Zhang, L. H. Li, T. Meng, K. Chang, and G. Van den Broeck (2023) On the paradox of learning to reason from data. In IJCAI, p. 3365–3373. Cited by: Table 11. [37] M. J. Zhang and E. Choi (2025) Clarify when necessary: resolving ambiguity through interaction with LMs. In Findings of the NAACL, p. 5526–5543. Cited by: §B.1. [38] M. J. Zhang, W. B. Knox, and E. Choi (2025) Modeling future conversation turns to teach LLMs to ask clarifying questions. In ICLR, Cited by: §2. [39] Y. Zhou, S. Jiang, Y. Tian, J. Weston, S. Levine, S. Sukhbaatar, and X. Li (2025) Sweet-RL: training multi-turn LLM agents on collaborative reasoning tasks. arXiv preprint arXiv:2503.15478. Cited by: §2. [40] Z. Zhou, X. Feng, Z. Zhu, J. Yao, S. Koyejo, and B. Han (2025) From passive to active reasoning: can large language models ask the right questions under incomplete information?. In ICML, Cited by: Table 2, §1, §2, §2. Appendix A Ethics statement and broader impacts This work formalizes and measures multi-turn information seeking, supporting evaluation beyond final-answer accuracy: whether models recognize missing information, ask appropriate follow-up questions, and avoid unsupported guesses. Such evaluation may help develop interactive systems that are more transparent about uncertainty and more cautious under underspecification. The evaluation suite that instantiates our framework, MT-InfoSeek, is constructed from public or synthetically generated sources and does not require collecting private user data. At the same time, our results are diagnostic measurements on controlled tasks rather than evidence of deployment readiness. Although MT-InfoSeek includes clinical decision procedures and biological networks, these tasks serve only controlled evaluation, not real-world clinical or scientific decision-making. The suite also does not cover the full diversity of real information-seeking interactions and may reflect cultural, linguistic, or domain-specific assumptions. We have released code, data, and prompts to support reproducibility, auditing, and further stress-testing. Appendix B Additional motivation B.1 Underspecification and the inference gap Underspecification and ambiguity. Underspecification and ambiguity concern different stages of an interaction. An ambiguous request admits more than one interpretation, so the uncertainty lies in which problem the user intends to pose. An underspecified request poses its problem clearly and withholds what is needed to solve it [15, 37]. What is missing is information about the case, not the user’s intent. Why underspecification is difficult to detect. Ambiguity tends to declare itself, since the competing readings are present in the request. Underspecification leaves no such trace: users are rarely in a position to know what the model lacks, and a model can produce a confident answer by silently assigning presumptive values to variables it never queried. Multi-turn interaction compounds the problem, because an assumption adopted at an early turn conditions every turn that follows and surfaces, if at all, only in the final answer. The inference gap. Clinical medicine has studied this problem under its own name, the inference gap, defined as the distance between what is known at the point of care and the evidence required to reach a decision for the individual patient. Bridging it is treated as the leap clinicians make daily in fitting generalized clinical evidence to a particular case [9]. The gap is closed by acquiring what is missing, whether by asking the patient, ordering a test, or running a clinical study. These differ in cost and latency but share a common structure: each requires recognizing that the target is not yet determined, and then selecting an action expected to narrow the possibilities that remain consistent with what is already known. Strong inference describes the same procedure in scientific practice, where a crucial experiment is chosen for its capacity to exclude competing hypotheses [22]. Our information-seeking tasks sit above the act of acquisition: we ask whether a model recognizes that its context is insufficient and identifies what would resolve it, not how that information can be obtained. This is a simplification: all queries carry the same cost, and every problem admits a sufficient set by construction, whereas in practice acquisition costs vary and some gaps cannot be closed by any available evidence. What we measure comes first in any setting: a model that cannot tell what is missing will not ask for it, order it, or design an experiment to obtain it. B.2 LLMs can still achieve high accuracy even with limited information Table 1: Performance of Qwen3-30B-A3B-Thinking-FP8 in the full MediQ dataset, with limited or full information provided to the LLM in prompt, and no interaction with user allowed. CRAFT_MD MedQA-dev MedQA-test Limited information 0.69 0.6 0.58 Full information 0.91 0.88 0.86 Proportion* 74% 62% 61% * Proportion of questions where the model selects the correct choice in at least 2/4 repeats (limited information, no interaction). Prompts: System Prompt You are a medical doctor trying to reason through a real-life clinical case. Based on your understanding of basic and clinical science, medical knowledge, and mechanisms underlying health, disease, patient care, and modes of therapy, respond according to the task specified by the user. Base your response on the current and standard practices referenced in medical guidelines. User Prompt A patient comes into the clinic presenting with a symptom as described in the conversation log below: PATIENT INFORMATION: initial_or_full_info QUESTION: question OPTIONS: options YOUR TASK: Given the information so far, you MUST produce a factual conclusion. Pick an option and respond ONLY with the letter choice and NOTHING ELSE. Do NOT ask any questions. Do NOT provide any explanations or rationales. Table 2: Comparison with existing benchmarks for interactive information seeking. ✓, △ , and ✗ denote full, partial or judge-mediated, and no direct support, respectively. Multi-turn: evaluation involves multiple interaction turns. Proactive: the model must actively ask questions or choose information-gathering actions. Obj. Query: objective labels are provided for what information should be queried. Timing/Order: the benchmark evaluates when to ask, when to stop, or the order of acquired information. Target Ctrl.: multiple compatible target instances are evaluated under the same initial information to control target-specific bias. Benchmark Multi-turn Proactive Obj. Query Timing/Order Target Ctrl. Domains QuestBench [15] ✗ ✓ ✓ ✗ ✗ Logic, planning, math AR-Bench[40] ✓ ✓ △ △ ✗ Puzzles, numbers Active Task Disamb.[12] ✓ ✓ ✗ ✗ ✗ 20Q, code MediQ[17] ✓ ✓ ✗ △ ✗ Clinical QA CRAFT-MD[10] ✓ ✓ ✗ △ ✗ Clinical diagnosis LLMs Get Lost[13] ✓ ✗ ✗ △ ✗ Code, DB, math, NLG Interactive Bench.[35] ✓ ✓ △ △ ✗ Logic, math, games MT-InfoSeek (Ours) ✓ ✓ ✓ ✓ ✓ Math, logic, bio, clinical, 20Q Appendix C Formalization and evaluation details C.1 Formal definitions We define an information-seeking problem as a CSP P=⟨,,,,Y⟩,P= ,D,C,A,Y , where: (i) =Xii=1NX=\X_i\_i=1^N is a finite set of variables, (i) =ii=1ND=\D_i\_i=1^N is a family of domains, where iD_i is the domain of XiX_i, (i) =cj(Xii∈Ij)j=1MC=\c_j(\X_i\_i∈ I_j)\_j=1^M is a set of constraints, where each cjc_j is a Boolean predicate over a subset of variables, (iv) =⋀i∈I(Xi=xi)A= _i∈ I_ known(X_i=x_i) is the known partial assignment on a subset I⊆[N]I_ known [N], with xi∈ix_i _i, (v) Y is the target variable whose value we wish to determine. We assume that (,)(C,A) is satisfiable. Let Ω(P) (P) denote the set of full assignments ω over X that satisfy both C and A. For ω∈Ω(P)ω∈ (P), we write Y(ω)Y(ω) for the value of the target variable under ω. Definition C.1 (Known). Let ψ be a conjunction of variable assignments consistent with (,)(C,A). We say that the target variable Y is known under ψ if all feasible assignments satisfying ψ agree on the value of Y: Known(Y∣ψ)⇔∀ω1,ω2∈Ω(P),(ω1⊨ψ∧ω2⊨ψ)⇒Y(ω1)=Y(ω2).Known(Y ψ) ∀ _1, _2∈ (P),\ ( _1 ψ _2 ψ) Y( _1)=Y( _2). We write dom()dom(A) for the set of variables assigned in A. Let (P)=∖(dom()∪Y)U(P)=X (dom(A)∪\Y\) denote the queryable variables of P. Definition C.2 (Sufficient set). For S⊆(P)S (P), we say S is sufficient to determine Y under A if for every partial assignment s to S consistent with (,)(C,A), we have Known(Y∣∧(S=s)).Known(Y (S=s)). Definition C.3 (Underspecification [15]). A problem P is underspecified if the target variable cannot be determined from the current information alone, i.e., ¬Known(Y∣) (Y ). We can now formalize multi-turn information-seeking on top of the preliminaries above. Definition C.4 (Minimal sufficient set). Let P=⟨,,,,Y⟩P= ,D,C,A,Y be an underspecified problem. A set of variables S⊆(P)S (P) is a minimal k-sufficient set for P if: 1. Cardinality: |S|=k|S|=k. 2. Sufficiency: S is sufficient to determine Y under A. 3. Global minimality: No set S′⊆(P)S (P) with |S′|<k|S |<k is sufficient to determine Y under A. Evidently, k is unique for an underspecified problem and characterizes the degree of underspecification of the problem. We term such problem with a degree of underspecification of k a k-underspecified problem. For each compatible value y∈Y(ω):ω∈Ω(P),y∈\Y(ω):ω∈ (P)\, we define a task instance as Ty=(P,y),T_y=(P,y), where y is the (hidden) ground-truth value of the target variable Y. Thus, a single problem P induces a family of task instances, one for each compatible target value. Importantly, we also define task-level degree of underspecification for TyT_y. Definition C.5 (Task-level degree of underspecification). Let P=⟨,,,,Y⟩P= ,D,C,A,Y be an underspecified problem with problem-level degree of underspecification k, and let (P) MSS(P) denote the collection of all minimal k-sufficient sets for P. For a task instance Ty=(P,y)T_y=(P,y), its task-level degree of underspecification is k(Ty):=min|W|: k_ task(T_y):= \|W|: ∃S∈(P),W⊆S,∀ω∈Ω(P), ∃ S∈ MSS(P),\ W S,∀ω∈ (P), Y(ω)=y⇒Known(Y∣∧(W=ω|W)). Y(ω)=y \! (Y (W=ω|_W) ) \. Evidently, k(Ty)k_ task(T_y) can be smaller than the problem-level degree of underspecification of the corresponding problem P. For example, consider the problem P=⟨,,,,Y⟩P= ,D,C,A,Y with =X1=1⇒Y=y1,X1=0∧X2=1⇒Y=y2,X1=0∧X2=0⇒Y=y3,C=\X_1=1 Y=y_1,\;\;X_1=0 X_2=1 Y=y_2,\;\;X_1=0 X_2=0 Y=y_3\, =∅A= , and target variable Y. This is a 2-underspecified problem. However, for the task instance Ty1T_y_1, querying only the value of X1X_1 is sufficient to derive Y=y1Y=y_1. Note, in certain cases, there can be a set of variables whose cardinality is smaller than k_ task, but can still solve the task. This is due to the existence of target value-specific shortcuts, but they are not subset of any of the minimal sufficient sets of the problem. C.2 Multi-turn interaction formalization To formalize the multi-turn setup, fix a task instance TyT_y, a model M, and an information source O. The model is initialized with the problem P only. Accordingly, the initial interaction history is ℋ0=P.H_0=P. At turn t, the model generates a reasoning trace RtR_t and a query QtQ_t conditioned on the current history: (Rt,Qt)=M(ℋt−1).(R_t,Q_t)=M(H_t-1). Here, QtQ_t requests the value of some variable X(t)∈(P)X^(t) (P). The information source then returns a response It=O(Ty,Qt).I_t=O(T_y,Q_t). The interaction history is updated as ℋt=ℋt−1∪(Rt,Qt,It).H_t=H_t-1∪\(R_t,Q_t,I_t)\. The interaction terminates when the model stops querying and instead outputs a reasoning trace RfinalR_final and a prediction y y for the target value of Y. The full interaction is therefore ℋM(Ty)=((R1,Q1,I1),…,(RT,QT,IT),(Rfinal,y^)).H_M(T_y)= ((R_1,Q_1,I_1),…,(R_T,Q_T,I_T),(R_final, y) ). C.3 Evaluation metrics We consider the following metrics for each problem setup: • Degree of underspecification: Accuracy (degree of underspecification), predicted k less than ground-truth k, predicted k greater than ground-truth k. • Missing variables: For each problem P, we use a single ground-truth minimal sufficient set S=X(1),…,X(k)S=\X^(1),…,X^(k)\. Let the model-predicted variable set be S S. We define the following metrics: (1) Accuracy (missing variables) = S^=SI\ S=S\, (2) Jaccard similarity = |S^∩S||S^∪S| | S∩ S|| S∪ S|. • Task-solving: For a task TyT_y induced from a problem P with minimal sufficient set S=X(1),X(2),…,X(k),S=\X^(1),X^(2),…,X^(k)\, let model prediction be y y, and let the ordered variables queried by the model be Q^=(X^(1),…,X^(T)), Q=( X^(1),…, X^(T)), where T is the last turn the model queries. Let the deduplicated query sequence be Q^uniq=Unique(Q^), Q^uniq=Unique( Q), i.e., the ordered list obtained from Q Q by removing repeated queries while preserving first-occurrence order. Let the hit subsequence of Q Q be Q^∗=(X^∈Q^uniq:X^∈S), Q^*=(\, X∈ Q^uniq: X∈ S\,), i.e., the ordered list of queried variables that belong to S. For ClinGuide-MT, let the ordered sufficient variables be Q=(X(1),X(2),…,X(k)).Q=(X^(1),X^(2),…,X^(k)). We then define the following metrics: – Task completion: (1) Accuracy: y^=yI\ y=y\, (2) Final sufficiency: Known(Y∣ℋT)I\Known(Y _T)\, (3) Turn to sufficiency: mintt:Known(Y∣ℋt)=1 _t\t:I\Known(Y _t)\=1\ (for final-sufficient runs only), (4) Total turns: T. – Turn queries (unordered): (1) First-turn hit: X^(1)∈SI\ X^(1)∈ S\, (2) Second-turn hit: X^(2)∈S∖X^(1)I\ X^(2)∈ S \ X^(1)\\, (3) Query correctness: defines the proportion of queried variables that belong to MSS QueryCorr(Q^)=1T∑i=1TX^(i)∈S.QueryCorr( Q)= 1T _i=1^TI\ X^(i)∈ S\. (4) Query coverage: measures the fraction of MSS variables that have been successfully queried QueryCov(Q^)=|Q^∗|k∈[0,1]QueryCov( Q)= | Q^*|k∈[0,1]. – Turn queries (ordered, in ClinGuide-MT only): Query order correctness: we evaluate the correctness of the query order using the Damerau-Levenshtein distance, which measures the minimum number of insertions, deletions, substitutions, and adjacent transpositions required to transform one sequence into another. Here, we compare the sequence of Q^∗ Q^* with the ground-truth ordered sequence Q using the normalized distance: dDL(Q^∗,Q)d_DL( Q^*,Q). We define order correctness as a normalized similarity score: OrdCorr(Q^)=1−dDL(Q^∗,Q)max(|Q^∗|,|Q|)∈[0,1].OrdCorr( Q)=1- d_DL( Q^*,Q) (| Q^*|,|Q|)∈[0,1]. Table 3 summarizes all evaluation metrics used throughout the paper. Table 3: Glossary of evaluation metrics. Used in: L=Logic-Q-MT, G=GeneReg-MT, M=GSME-Q-MT/-Ext, C=ClinGuide-MT, 20Q=20 Questions. k/k^k/ k: true/predicted degree of underspecification; S: ground-truth MSS (S S: predicted); Q Q: variables queried over T turns, Q^∗ Q^*: those in S; Q: order-dependent sufficient sequence (ClinGuide-MT); ℋtH_t: history through turn t; y^/y y/y: predicted/true target; ptp_t: belief over 20Q candidates. Metric Notation Description Used in (A) Uncertainty awareness (problem-level) Degree accuracy k^=kI\ k=k\ Predicted degree of underspecification matches ground truth. L Under-prediction rate k^<kI\ k<k\ Predicts fewer missing variables than required. L Over-prediction rate k^>kI\ k>k\ Predicts more missing variables than required. L MSS accuracy S^=SI\ S=S\ Predicted variable set equals the MSS. L Jaccard similarity |S^∩S|/|S^∪S|| S∩ S|/| S∪ S| Overlap between predicted set and MSS. L Recall |S^∩S|/|S|| S∩ S|/|S| Fraction of MSS variables recovered. L (B) Task completion (sequential task-solving) Final accuracy y^=yI\ y=y\ Final answer matches the hidden target. L, G, M, C, 20Q Final sufficiency Known(Y∣ℋT)I\Known(Y _T)\ Acquired information uniquely determines the target. L, G, M Turn to sufficiency mintt:Known(Y∣ℋt) _t\t:Known(Y _t)\ Earliest turn at which information becomes sufficient. L, G Total turns T Interaction turns before committing to an answer. L, G, M, C, 20Q (C) Query behavior (turn-level) First-turn hit X^(1)∈SI\ X^(1)∈ S\ First query is an MSS variable. L, G Second-turn hit X^(2)∈S∖X^(1)I\ X^(2)∈ S \ X^(1)\\ Second query is a new MSS variable. L, G Query correctness 1T∑i=1TX^(i)∈S 1T _i=1^TI\ X^(i)∈ S\ Proportion of queries targeting sufficient variables. L, G, C Query coverage |Q^∗|/k| Q^*|/k Fraction of MSS variables queried. L,G,C Query order correctness 1−dDL(Q^∗,Q)max(|Q^∗|,|Q|)1- d_DL( Q^*,Q) (| Q^*|,|Q|) Normalized Damerau–Levenshtein similarity to the ground-truth order. C Over-questioning rate — Keeps querying after information is already sufficient. L, G, M (D) Reasoning-trace (CoT) diagnostics MSS relative mention rate R=#MSS vars planned#queryable vars plannedR= \#MSS vars planned\#queryable vars planned Among variables the model considers asking about, the share that belong to the MSS (R=0R=0 if none). L, G Awareness of underspecification — Binary flag that more information is needed, without naming a variable. L, G (E) 20Q information-theoretic metrics Entropy H(pt)=−∑cpt(c)logpt(c)H(p_t)=- _cp_t(c) p_t(c) Remaining uncertainty over candidate targets. 20Q Expected information gain (EIG) EIG(qt)=H(pt)−a[H(pt+1(a))]EIG(q_t)=H(p_t)-E_a\! [H(p_t+1^(a)) ] Expected entropy reduction over answers a (mutual information I(Y;At∣qt)I(Y;A_t q_t)). 20Q Normalized EIG (nEIG) EIG(qt)/(H(pt)+ϵ)EIG(q_t)/(H(p_t)+ε) Expected fraction of uncertainty removed; question-informativeness score. 20Q Pass mass ∑c:g(c,qt)=passpt(c) _c:g(c,q_t)= passp_t(c) Belief mass a question cannot cleanly split by yes/no. 20Q C.4 Information source and oracle design To test LLM’s information seeking ability with different types of information sources, we design three oracles that respond to queries from LLMs. • Adversarial oracle: Returns a deterministic value that is consistent with the problem constraints but chosen to maximally delay identification of the target outcome, i.e., preserving as many candidate outcomes as possible. • Random oracle: Samples a value from the set of assignments consistent with the problem constraints. When the queried variable is not uniquely determined, the oracle may respond with “not sure”, reflecting ambiguity. • Cooperative oracle: Returns a deterministic value consistent with the ground-truth assignment that most directly reduces uncertainty about the target outcome. Note that: (1) the adversarial and cooperative oracles both act greedily (one-step look ahead). (2) While the cooperative oracle yields strictly easier evaluations, the adversarial oracle does not necessarily require more queries than the random oracle. The random oracle may introduce ambiguity through "not sure" responses, whereas the adversarial oracle must respond with a deterministic answer. For controlled tasks, we use adversarial oracles to evaluate a worst-case information-seeking setting, where the oracle answers consistently with the hidden target while avoiding unnecessary disclosures. This prevents models from benefiting from overly helpful responses and tests whether they can select target-relevant queries under realistic constraints such as privacy and limited observability. As sanity checks, models perform worse with random or adversarial oracles than with cooperative oracles (Appendix Fig. 10), and adversarial-oracle results are more consistent across True- and False-target variants than cooperative-oracle (Appendix Figs. 11,12). We do not carry models’ previous turn reasoning traces to the next turn inference as it could lead to degradation in performance for specific models (Appendix Fig. 13). Figure 10: Performance of LLMs in Logic-Q-MT task-solving with different oracle types. coop stands for cooperative, rand stands for random, and adv stands for adversarial. With a budget of 10 turns, 1 query per turn allowed. p-values from two-sided paired T-test. Figure 11: Correlation between performances on tasks with True target variable values and with False target variable values for LLMs in Logic-Q-MT task-solving. Runs are with adversarial oracles and different budget (1 turn x 4 queries, 4 turns x 1 query, 10 turns x 1 query) and alternative minimal sufficient set variable forbiddance statuses (forbid, allow). Due to (realistic) budget constraints, commercial models are only run with forbid. r from Pearson’s correlation. Figure 12: Correlation between performances on tasks with True target variable values and with False target variable values for LLMs in Logic-Q-MT task-solving. Runs are with cooperative oracles and different budget (1 turn x 4 queries, 4 turns x 1 query, 10 turns x 1 query) and alternative minimal sufficient set variable forbiddance statuses (forbid, allow). Due to (realistic) budget constraints, commercial models are only run with forbid. r from Pearson’s correlation. Figure 13: Performance of Qwen3-30B-A3B-Thinking-FP8 in Logic-Q-MT task-solving, with or without thinking traces appended in conversation history to the next turn. Runs are with different budget (1 turn x 4 queries, 4 turns x 1 query, 10 turns x 1 query), oracle type (adversarial, random, cooperative), and alternative minimal sufficient set variable forbiddance (forbid, allow). C.5 Robustness to oracle response policies In the structured domains, every oracle response remains consistent with the underlying CSP regardless of the response policy: the adversarial, random, and cooperative oracles defined in Appendix C.4 differ only in how they select among valid responses. To test whether the reported findings depend on the adversarial policy used in the main experiments, we reran GeneReg-MT under the random and cooperative oracles for four representative models (Qwen3-4B-Thinking, Qwen3-30B-A3B-Thinking-FP8, GPT-5-mini, and gpt-oss-20B-high). First, the decline with the degree of underspecification persists: from k=1k=1 to k=4k=4, final sufficiency decreased for all four models under both oracles, by 29.7–41.9 p under the random oracle and 25.0–39.0 p under the cooperative oracle. Second, the turn-budget effect persists: 54 of 64 fitted budget slopes were positive, with most exceptions in the marker-identification task. Third, recovery from a first-turn miss persists: among episodes whose first query missed but whose second query hit, final sufficiency was 0.89–1.05× that of first-turn-hit episodes under the random oracle and 0.92–1.09× under the cooperative oracle, and after adjusting for GeneReg-MT task type and k, the recovery association was positive for all eight model–oracle pairs and reached p<0.05p<0.05 for six of the eight. Oracle type does change absolute difficulty as expected: cooperative responses yielded the highest pooled final sufficiency for all four models. However, it does not account for the qualitative conclusions above. C.6 Reliability of LLM-based oracles Logic-Q-MT, GSME-Q-MT, and GeneReg-MT use deterministic algorithmic oracles, so their responses are correct by construction. Only the open-ended ClinGuide-MT and 20Q settings rely on an LLM-based oracle, a design shared with interactive clinical benchmarks [17]: in 20Q, an oracle LLM answers free-form questions about the hidden target (yes, no, or pass), and in ClinGuide-MT, an oracle LLM decides whether a model’s free-text question matches an information item on the guideline-derived diagnostic pathway [7]. Because LLM outputs can vary with sampling and input formulation [26, 19], we evaluate the reliability of these LLM-mediated information sources along four axes: within-oracle consistency, cross-oracle agreement, human validation, and impact on task outcomes. Within-oracle consistency. For 20Q, we resampled the oracle’s response to each logged question three times at temperature 0.6. All three samples agree on 91.9%–95.6% of questions (κ≈0.91κ≈ 0.91–0.940.94; Table 4), and most variation involves an uncertainty label rather than conflicting substantive answers. For ClinGuide-MT, we replayed each oracle on identical inputs (system prompt, patient context, and model query), reported separately for each evaluated answerer model. Repeated-response agreement ranges from 94.0% to 97.7% (Table 5), with GPT-5-mini—the oracle used in the main ClinGuide-MT experiments—the more stable of the two; the maximum variation is 3.7 p and the relative ordering of answerer models is unchanged. Most inconsistencies are conservative shifts to or from “Not sure” (80.6%–95.6% of inconsistent cases) rather than switches between substantive answers. Table 4: Within-oracle consistency of the 20Q oracles: percentage of questions on which three responses sampled at temperature 0.6 all agree, with confidence intervals in brackets. Oracle Common (%) Thing (%) Qwen3-30B-A3B-Instruct-FP8 95.4 [93.6, 97.1] 95.6 [93.8, 97.2] GPT-5-mini 92.7 [90.5, 94.9] 91.9 [89.5, 94.3] Table 5: Within-oracle consistency of the ClinGuide-MT oracles when replayed on identical inputs (system prompt, patient context, and model query), reported separately for each evaluated answerer model, with confidence intervals in brackets. The last column is the share of inconsistent cases involving a shift to or from “Not sure”. Oracle Answerer Agreement (%) “Not sure” share (%) GPT-5-mini Qwen3-30B-A3B-Thinking-FP8 97.7 [96.6, 98.7] 86.8 GPT-5-mini GPT-5 97.3 [96.6, 98.4] 80.6 GPT-5.4 Qwen3-30B-A3B-Thinking-FP8 94.1 [92.7, 96.5] 95.6 GPT-5.4 GPT-5 94.0 [92.8, 96.2] 90.8 Cross-oracle agreement. For 20Q, we regenerated responses to the same 545 questions using alternative oracle models: GPT-5-mini and GPT-5.4 agree with Qwen3-30B-A3B-Instruct-FP8 on 93.4% and 94.1% of responses, respectively. Most disagreements concern the boundary between a decisive answer and “pass” rather than reversals between substantive answers; Table 6 shows representative boundary cases together with an independent human label. For ClinGuide-MT, we compared the two oracle choices (GPT-5-mini and GPT-5.4) on identical inputs, separately for each evaluated answerer model; the two oracles agree on 94.0% of responses for both answerer models (Table 7). Table 6: Representative 20Q cross-oracle disagreements. Oracle responses are listed in the order Qwen3-30B-A3B-Instruct-FP8 / GPT-5-mini / GPT-5.4; the human label comes from an independent annotator. Disagreements concentrate on category boundaries rather than reversals between substantive answers. Target Question Oracle responses Human T-Rex Is T-Rex a living thing? no / no / yes yes Christmas tree Is Christmas tree a living thing? no / pass / pass pass Mount Rushmore Is Mount Rushmore man-made? yes / pass / pass pass Table 7: Cross-oracle agreement in ClinGuide-MT: percentage of identical inputs on which the two oracle choices (GPT-5-mini and GPT-5.4) return the same response, with confidence intervals in brackets. Answerer GPT-5-mini vs. GPT-5.4 agreement (%) Qwen3-30B-A3B-Thinking-FP8 94.0 [92.4, 96.4] GPT-5 94.0 [93.1, 95.9] Human validation. For 20Q, a graduate-level annotator independently labelled 300 questions, evenly split between Common and Thing, without seeing the oracle responses. Human–oracle agreement is high for all three oracle models (Table 8), and disagreements again concentrate on category boundaries or partially applicable questions. For ClinGuide-MT, we manually audited 200 oracle responses and labelled each as correct, a clear mismatch, or borderline, where borderline means that the model’s question has meaningful clinical overlap with a desired question, so that either matching it or returning “Not sure” can be reasonable (Table 9). Table 8: Human–oracle agreement on 20Q: fraction of 300 independently annotated questions (150 per dataset) on which the human label matches each oracle’s response. Dataset Qwen3-30B-A3B-Instruct-FP8 GPT-5-mini GPT-5.4 Common 0.907 0.953 0.960 Thing 0.933 0.940 0.960 Table 9: Manual audit of 200 ClinGuide-MT oracle responses. Borderline denotes questions with meaningful clinical overlap with a desired question, where either matching or returning “Not sure” can be reasonable. Answerer Correct (%) Clear mismatch (%) Borderline (%) GPT-5 91 5 4 Qwen3-30B-A3B-Thinking-FP8 85 9 6 Impact on task outcomes. Finally, we assess whether residual oracle error could affect the reported conclusions. For 20Q, we audited the 1,669 turns for which two independent reference models (Claude-Opus-4.8 and GPT-5.6-sol) unanimously assigned a definite Yes/No label. GPT-5-mini agreed with this reference panel on 99.9% of the audited turns, corresponding to an error rate of 0.1%, and 110 of 111 audited episodes contained no identifiable oracle error, whereas the guesser failed on 72% of episodes; oracle errors therefore cannot explain the observed 20Q failure rate or the main comparative conclusions. For ClinGuide-MT, the manual audit identified 7% clear mismatches and 5% borderline matches pooled across the two answerer models. The dominant error mode is overmatching a related but non-equivalent question, such as mapping a query about hair-loss type to a duration-specific question, while borderline cases involve meaningful clinical overlap without being clear paraphrases; Table 10 shows representative cases. Table 10: Representative ClinGuide-MT oracle errors from the manual audit of 200 responses. Model question Oracle-matched question Human verdict Hair-loss type Hair-loss duration under one year Mismatch: type ≠ duration Ataxia with falling Cause of gait abnormality Mismatch: symptom ≠ mechanism Specific question about mania Broader composite psychiatric screen Borderline: partial overlap, not a clear paraphrase Appendix D Dataset construction details Dataset statistics can be found in Table 11. Table 11: Dataset statistics by degree of underspecification. Columns under Problems and Tasks report the total count and the count for each k; “–” denotes not applicable. Dataset # Problems # Tasks Source Total k=1k=1 k=2k=2 k=3k=3 k=4k=4 Total k=1k=1 k=2k=2 k=3k=3 k=4k=4 Logic-Q-MT 600 200 200 200 0 1200 400 400 400 0 [36] GeneReg-MT 800 – – – – 2326 451 626 729 520 38 GRNs [11] GSME-Q-MT 2956 1067 884 709 296 2956 1067 884 709 296 [15] GSME-Q-MT-Ext 524 134 144 123 123 524 134 144 123 123 Synthetic ClinGuide-MT 370 – – – – 1595 521 477 370 227 59 algorithms [7, 30] 20Q 1 – – – – 405 – – – – [8] D.1 Logic-Q-MT In the 1-underspecified problem construction pipeline [15], each pair of true-target and false-target assignments (i(y),j(¬y))(A_i^(y),A_j^( y)) is examined, and pairs differing only in the assignment of one variable xdx_d are collected for further validation: after removing xdx_d, the shared context (i(y)∖xd)∧(j(¬y)∖xd)(A_i^(y) x_d) (A_j^( y) x_d) should not already determine the target value. However, when extending to larger k, merely collecting the variables whose assignments differ between (i(y),j(¬y))(A_i^(y),A_j^( y)) is neither sufficient nor necessary for identifying minimal k-sufficient sets. For example, XOR/XNOR-style dependencies at k=2k=2 cannot be captured by a single pairwise flip criterion. We therefore design a recursive construction algorithm for candidate k-sufficient CSPs (Algorithm 1), followed by a feasibility-aware validator (Algorithm 2). For Logic-Q-MT, the SimpleLogic rules are represented as Horn CNF clauses: a rule (x1∧⋯∧xm)⇒y(x_1 ·s x_m) y is stored as (¬x1∨⋯∨¬xm∨y).( x_1 ·s x_m y). Thus, feasibility and entailment can be decided by Horn-SAT. In our implementation, we use unit propagation with empty-clause detection to test feasibility, and use refutation to test whether a target value is forced. Concretely, for a partial assignment ψ, define (ψ,Y)=⊥,∧ψ is infeasible,1,∧ψ⊧Y,0,∧ψ⊧¬Y,?,otherwise. Force_C(ψ,Y)= cases ,&C ψ is infeasible,\\ 1,&C ψ Y,\\ 0,&C ψ Y,\\ ?,&otherwise. cases For Horn CNF, this is computed by unit propagation: feasibility is checked by whether unit propagation derives an empty clause; Y is forced true iff ∧ψ∧¬YC ψ Y is infeasible, and forced false iff ∧ψ∧YC ψ Y is infeasible. Let (,S,Y) Suff(A,S,Y) denote the predicate that S is sufficient to determine Y under context A: (,S,Y)⇔∃s feasible for Sand∀s feasible for S,(∧(S=s),Y)∈0,1. Suff(A,S,Y) ∃ s feasible for S\;\;and\;\;∀ s feasible for S,\ Force_C(A (S=s),Y)∈\0,1\. From a complete SimpleLogic problem, we first obtain candidate minimal 11-sufficient sets using an improved algorithm based on [15]. Assume that at step k−1k-1 we have obtained candidate minimal (k−1)(k-1)-sufficient sets (k−1,k−1)(A_k-1,S_k-1). For each assigned literal ℓk=(xk=ak) _k=(x_k=a_k) in k−1A_k-1, we remove it from the context and add its variable to the query set: k=k−1∖ℓk,k=k−1∪xk.A_k=A_k-1 \ _k\, _k=S_k-1∪\x_k\. Since k−1=k∧(xk=ak)A_k-1=A_k (x_k=a_k), sufficiency of k−1S_k-1 under k−1A_k-1 already verifies the branch xk=akx_k=a_k. We therefore additionally check the flipped branch: (k∧(xk=flip(ak)),k−1,Y). Suff\! (A_k (x_k=flip(a_k)),S_k-1,Y ). This yields a candidate k-sufficient set. We then apply global minimality and feasibility-aware validation over the final query space. Algorithm 1 Recursive construction of candidate k-sufficient sets Input: Horn CNF constraints C; target Y; forcing oracle Force_C; candidate minimal (k−1)(k-1)-sufficient sets ℳk−1M_k-1. Output: Candidate k-sufficient sets ℳkM_k. for all (k−1,k−1)∈ℳk−1(A_k-1,S_k-1) _k-1 do for all assigned literals ℓk=(xk=ak)∈k−1 _k=(x_k=a_k) _k-1 do k←k−1∖ℓkA_k _k-1 \ _k\ k←k−1∪xkS_k _k-1∪\x_k\ Non-triviality: the reduced context alone should not determine Y. if (k,Y)∈0,1 Force_C(A_k,Y)∈\0,1\ then continue end if The branch xk=akx_k=a_k is inherited from the (k−1)(k-1)-sufficient item. Check the flipped branch. if ¬(k∧(xk=flip(ak)),k−1,Y) Suff\! (A_k (x_k=flip(a_k)),S_k-1,Y ) then continue end if Efficient candidate-level minimality check. ok←trueok← true for all ⊆(P(,k))U (P(C,A_k)) with ||=k−1|U|=k-1 do if (k,,Y) Suff(A_k,U,Y) then ok←falseok← false break end if end for if okok then ℳk←ℳk∪(k,k)M_k _k∪\(A_k,S_k)\ end if end for end for This recursive procedure is an efficient candidate generator. Because infeasible assignments and alternative sufficient sets can create false positives, we apply the feasibility-aware validator in Algorithm 2. Algorithm 2 Feasibility-aware validation for Logic-Q-MT Input: CSP P with Horn CNF constraints C and context kA_k; candidate set k=x1,…,xkS_k=\x_1,…,x_k\; target Y; askable universe (P)U(P); forcing oracle Force_C. Output: accept/reject. ←∅T← A partial truth table over feasible assignments to kS_k. Step 1: Feasibility-aware sufficiency. for all a∈0,1ka∈\0,1\^k do ϕa←⋀i=1k(xi=ai) _a← _i=1^k(x_i=a_i) z←(k∧ϕa,Y)z← Force_C(A_k _a,Y) if z=⊥z= then continue Discard infeasible assignment. else if z=?z=? then return reject kS_k is not sufficient. else [a]←zT[a]← z end if end for if =∅T= then return reject end if Step 2: Essentiality of each variable in kS_k. for j=1j=1 to k do essential←false essential← false for all b∈0,1k−1b∈\0,1\^k-1 assignments to k∖xjS_k \x_j\ do Let a(0)=(xj=0,b)a^(0)=(x_j=0,b) and a(1)=(xj=1,b)a^(1)=(x_j=1,b). if a(0)∈dom()a^(0) (T) a(1)∈dom()a^(1) (T) [a(0)]≠[a(1)]T[a^(0)] [a^(1)] then essential←true essential← true break end if end for if essential=false essential= false then return reject end if end for Step 3: Global minimality against alternative query sets. for all ⊆(P)U (P) with ||=k−1|U|=k-1 do if (k,,Y) Suff(A_k,U,Y) then return reject end if end for return accept For Logic-Q-MT, Force_C is implemented by Horn-SAT: unit propagation detects infeasible branches, and the entailment of Y or ¬Y Y is checked by refutation. Since sufficiency is monotone in the queried variable set, checking all (k−1)(k-1)-subsets rules out all smaller sufficient sets as well. Brute-force essentiality check. We further clarify the need of the essentiality validation. Consider 2=x1,x2S_2=\x_1,x_2\ and suppose the feasible assignments over (x1,x2,y)(x_1,x_2,y) are exactly Ω=(0,0,0),(1,1,1),(1,0,1), =\(0,0,0),(1,1,1),(1,0,1)\, where the missing combination (0,1)(0,1) is infeasible due to contradictions with the constraints. Then y does not depend essentially on x2x_2: there is no pair of feasible assignments that agrees on x1x_1 but flips x2x_2 and changes y. However, a recursive subset-based check can fail to expose this issue when it never explicitly conditions on the infeasible combination involving the removed variable. Such a procedure may incorrectly treat 2S_2 as minimal. This motivates our feasibility-aware essentiality validation, which enumerates all assignments to kS_k, removes infeasible rows, and checks essentiality directly on the remaining table. Recursive coverage is not guaranteed over non-Cartesian feasible domains. A general complete coverage using the recursive algorithm is not guaranteed once we allow arbitrary CSP rules (constraints) over the variables (i.e., the feasible set is an arbitrary relation rather than a full Cartesian product). In particular, classical results in the spirit of Salomaa apply to total functions over Cartesian domains, but need not extend to arbitrary constraint relations 22 2 See, statements that for an n-ary function f:An→Bf:A^n→ B depending on all variables, there exists a coordinate whose fixing preserves dependence on the remaining n−1n-1 variables; this relies on the full Cartesian domain assumption [25] (restated in a convenient form by Couceiro and Lehtonen [4]).. As a counterexample, consider the following k=4k=4 case. Let a,b,c,d,y∈0,1a,b,c,d,y∈\0,1\ and =⊤A= . Define the CSP extensionally by allowing exactly the following nine assignments (ordered as (a,b,c,d,y)(a,b,c,d,y)): Ω= \;=\;\ (0,0,0,0,0),(0,0,0,1,0),(0,0,1,0,1),(0,1,0,0,1),(1,0,0,1,1), (0,0,0,0,0),(0,0,0,1,0),(0,0,1,0,1),(0,1,0,0,1),(1,0,0,1,1), (1,0,1,0,1),(1,0,1,1,1),(1,1,1,0,0),(1,1,1,1,1). (1,0,1,0,1),(1,0,1,1,1),(1,1,1,0,0),(1,1,1,1,1)\. (i) a,b,c,d\a,b,c,d\ is globally minimal 44-sufficient for y under A. First, y is not known under =⊤A= since Ω contains both y=0y=0 and y=1y=1 solutions. Second, knowing all of (a,b,c,d)(a,b,c,d) determines y because each feasible (a,b,c,d)(a,b,c,d) pattern occurs with a unique y in Ω . Finally, no 3-subset suffices: for each 3-subset there exist two feasible assignments agreeing on those three variables but disagreeing on y, e.g., a,b,c: \a,b,c\:~ (1,1,1,0)↦y=0 vs. (1,1,1,1)↦y=1, (1,1,1,0) y=0\; vs. \;(1,1,1,1) y=1, a,b,d: \a,b,d\:~ (0,0,1,0)↦y=1 vs. (0,0,0,0)↦y=0, (0,0,1,0) y=1\; vs. \;(0,0,0,0) y=0, a,c,d: \a,c,d\:~ (0,1,0,0)↦y=1 vs. (0,0,0,0)↦y=0, (0,1,0,0) y=1\; vs. \;(0,0,0,0) y=0, b,c,d: \b,c,d\:~ (0,0,0,1)↦y=0 vs. (1,0,0,1)↦y=1. (0,0,0,1) y=0\; vs. \;(1,0,0,1) y=1. Hence the minimum sufficient size under A is 44, and a,b,c,d\a,b,c,d\ is globally minimal. (i) No single assignment reduces it to a globally minimal 33-sufficient problem. Conditioning on any single variable assignment collapses the instance so that the minimum sufficient size drops below 33: min-size(∧a=0)=2,min-size(∧a=1)=2, -size(A a=0)=2,\; -size(A a=1)=2,\; min-size(∧b=0)=2,min-size(∧b=1)=2, -size(A b=0)=2,\; -size(A b=1)=2, min-size(∧c=0)=2,min-size(∧c=1)=2, -size(A c=0)=2,\; -size(A c=1)=2,\; min-size(∧d=0)=2,min-size(∧d=1)=1. -size(A d=0)=2,\; -size(A d=1)=1. Therefore, although the original instance is globally minimal 44-sufficient, there exists no single variable/value assignment that produces a context whose globally minimal sufficient size is 33. This blocks complete coverage by a recursive k=3→4k=3→ 4 construction. D.2 GSME-Q-MT and GSME-Q-MT-Ext This section describes the construction of our GSME-based multi-turn information-seeking datasets. We first extend the original GSME-Q benchmark into a multi-turn setting, denoted as GSME-Q-MT, and then introduce GSME-Q-MT-Ext, an enriched variant generated from DAG-structured arithmetic programs. Figure 14: Complexity Across Task Settings. D.2.1 GSME-Q-MT construction GSME-Q-MT is derived from the original GSME-Q equation systems. For each problem, we identify base variables that are not defined by other equations, mask a subset of them, and validate whether the masked subset forms a minimal k-sufficient set for determining the target (Algorithm 3). This yields controlled multi-turn tasks where the model must ask for multiple missing quantities before solving the problem. Base-variable pool. For each original GSME-Q instance, we parse the equation system and identify the target variable y, the arithmetic constraints C, and the set of leaf or base variables. A base variable is a variable that is not produced as the output of any equation. These variables correspond to primitive quantities that can be directly provided in the problem statement. We exclude dataset-provided distractors from the base-variable pool used for constructing true missing conditions. We also require each resulting instance to retain a minimum number of revealed base variables, preventing degenerate contexts where the problem contains too little visible information. Dependency graph and relevant leaves. From the equation system, we construct a directed dependency graph. An edge points from an input variable to an output variable whenever the input is used in an arithmetic constraint defining the output. We compute the ancestor set of the target variable, denoted Anc(y)Anc(y). Let ℒL be the set of leaf variables. The goal-relevant leaf set is ℒrel=ℒ∩Anc(y).L_rel=L (y). Only variables in ℒrelL_rel are considered as true missing variables. This avoids treating structurally irrelevant distractors as necessary information. Minimal k-sufficient set construction. For a target value of k, we sample candidate held-out sets Sk⊆ℒrelS_k _rel with |Sk|=k|S_k|=k. For each candidate SkS_k, we reveal all relevant leaves outside SkS_k: k=x=vx:x∈ℒrel∖Sk.A_k= \x=v_x:x _rel S_k \. We retain SkS_k only if it satisfies the following three conditions: (1)¬Known(y∣k),(1)\ (y _k), (2)Known(y∣k∪x=vx:x∈Sk),(2)\ Known(y _k∪\x=v_x:x∈ S_k\), (3)∀S′⊂Sk,¬Known(y∣k∪x=vx:x∈S′).(3)\ ∀ S ⊂ S_k, (y _k∪\x=v_x:x∈ S \). The first condition enforces underspecification: the visible information alone is insufficient. The second condition enforces sufficiency: revealing the full held-out set makes the target uniquely determined. The third condition enforces global minimality, or strict necessity: no smaller subset of the held-out variables is enough. Candidate query set. Each instance is accompanied by a candidate set of queryable variables. This set contains the true missing variables SkS_k, dataset-provided distractors when available, and additional decoys. The decoys are selected to discourage superficial strategies. They may include variables that are derivable from already revealed information, variables that are structurally irrelevant to the target, or plausible quantities that appear in the problem but are not necessary for determining y. Thus, the model must distinguish necessary information from irrelevant or redundant information. Difficulty ranking. A single original problem may induce multiple valid held-out sets. When more than a fixed number of valid sets are found, we rank them by a difficulty score and keep the top instances. The score can incorporate structural and ambiguity-based factors, such as the maximum distance from held-out leaves to the target and the number of possible target values under the visible information. This avoids overrepresenting trivially easy masks. Algorithm 3 Constructing Minimal k-Sufficient GSME-Q-MT 0: Source GSME problems T; maximum degree kmaxk_ ; candidate budget N; keep-top M 0: Generated dataset ′T 1: ′←∅T ← 2: for each problem instance p∈p do 3: Parse variables X, domains D, constraints C, full assignment ω⋆ω , and target variable Y 4: Construct the dependency graph induced by C 5: Identify queryable variables relevant to Y: ←Leaves()∩Anc(Y)U (X) (Y) 6: for k=1k=1 to kmaxk_ do 7: if k>||k>|U| then 8: continue 9: end if 10: Sample up to N candidate sets S⊆S with |S|=k|S|=k 11: k←∅V_k← 12: for each candidate set S do 13: Define observed assignment S←X=ω⋆(X):X∈∖SA_S←\X=ω (X):X S\ 14: if Known(Y∣S)Known(Y _S) then 15: continue Y is already determined 16: end if 17: if there exists an assignment s to S consistent with (,S)(C,A_S) such that ¬Known(Y∣S∧s) (Y _S s) then 18: continue S is not sufficient 19: end if 20: if there exists S′⊂S ⊂ S such that, for every consistent assignment s′s to S′S , Known(Y∣S∧s′)Known(Y _S s ) then 21: continue S is not minimal 22: end if 23: k←k∪SV_k _k∪\S\ 24: end for 25: Rank kV_k by difficulty and keep the top M sets 26: for each kept set S∈kS _k do 27: y⋆←Y(ω⋆)y ← Y(ω ) 28: Rewrite p by masking variables in S 29: Construct the candidate query set from U 30: Emit sample τ=(PS,S,S,Y,y⋆,)τ=(P_S,A_S,S,Y,y ,U) 31: ′←′∪τT ∪\τ\ 32: end for 33: end for 34: end for 35: return ′T D.2.2 GSME-Q-MT-Ext construction Although GSME-Q-MT extends GSME-Q to multiple missing variables, the resulting problems remain limited by the structure of the original dataset. Many instances contain few variables, short dependency chains, and weak interactions among missing quantities. As a result, identifying the missing variables is often easy once the model parses the equation structure. To create a more discriminative testbed, we construct GSME-Q-MT-Ext (Algorithm 4). Latent program representation. Each GSME-Q-MT-Ext instance is generated from a directed acyclic graph G=(V,E)G=(V,E), where nodes V correspond to variables and edges E encode arithmetic dependencies. Leaf nodes represent primitive quantities. Internal nodes represent derived quantities defined by arithmetic rules. One node y∈Vy∈ V is designated as the goal variable. The graph is treated as the canonical latent structure of the problem, while the natural-language or symbolic problem statement is a surface rendering of this latent program. This representation gives direct control over structural properties, including the number of variables, the number of constraints, reasoning depth, branch-merge patterns, and the separation between goal-relevant and distractor variables. Controlled structural complexity. GSME-Q-MT-Ext controls complexity along four main axes. Depth is defined as the length of the longest directed path from a goal-relevant leaf variable to the target variable. To ensure that depth reflects actual reasoning requirements, we explicitly construct a goal-bearing backbone chain rather than merely adding disconnected equations. Second, we introduce branching and merge structures. A merge node is an internal variable whose value depends on multiple parent variables. Such nodes create situations where multiple upstream quantities jointly determine a downstream quantity. This is important for multi-turn evaluation because the model may need to acquire several missing leaves before the target becomes determined. Third, we include distractor subgraphs. A distractor subgraph is a valid arithmetic component that appears in the instance but is not an ancestor of the target. Distractor subgraphs increase structural clutter without changing the target value. They test whether the model can separate relevant missing information from plausible but unnecessary information. Fourth, we control the number of goal-relevant leaves. This is especially important for constructing large-k instances, because a problem must contain enough relevant primitive quantities to support a minimal k-sufficient held-out set. Generation pipeline. The GSME-Q-MT-Ext generation pipeline consists of five stages. Stage 1: sample structural targets. For each instance, we sample or specify target structural parameters, including the number of variables, the number of arithmetic rules, the target reasoning depth, the number of goal-relevant leaves, and the amount of distractor structure. Stage 2: build the goal-relevant subgraph. We first construct a backbone chain that guarantees the target reasoning depth. We then attach additional branches and merge nodes to create richer dependency patterns. The construction is biased toward the requested number of relevant leaves, ensuring that the instance can support the desired missing-information level k. Stage 3: add distractor subgraphs. We optionally add disconnected arithmetic components that do not affect the target variable. These components are valid and internally consistent, but none of their variables is an ancestor of y. They are included in the full problem representation and the query candidate pool, making the information-seeking task less reducible to surface matching. Stage 4: assign values by forward execution. We sample values for leaf variables and compute all internal node values by executing the DAG in topological order. Whenever division is used, we enforce divisibility constraints so that all generated values remain integer-friendly. Stage 5: validate and filter. Each generated instance is validated before being retained. We check that the graph is acyclic, that all arithmetic rules are numerically consistent, that the requested structural targets are satisfied, that the target has a valid ancestry structure, and that the target is solvable from full information. We then construct and validate minimal k-sufficient held-out sets following the same criterion used in GSME-Q-MT. Algorithm 4 GSME-Q-MT-Ext generation 0: Number of samples B; structural parameter ranges Θ ; maximum missing set size kmaxk_ ; candidate budget N; keep-top M 0: Generated dataset ExtT_Ext 1: Ext←∅T_Ext← 2: while |Ext|<B|T_Ext|<B do 3: Sample structural targets θ∼Θθ 4: Build a goal-bearing backbone chain with target depth specified by θ 5: Add branch and merge nodes to increase structural entanglement 6: Add optional distractor subgraphs disconnected from the target 7: Let G=(V,E)G=(V,E) be the resulting graph and choose target node y 8: Sample leaf values and compute internal values by topological forward execution 9: if G is not acyclic or any arithmetic constraint is invalid then 10: continue 11: end if 12: if G does not satisfy the requested structural targets then 13: continue 14: end if 15: Compute all leaves ℒallL_all 16: Compute relevant leaves ℒrel=ℒall∩Anc(y)L_rel=L_all (y) 17: Construct valid held-out sets 18: if no valid held-out set is found then 19: continue 20: end if 21: Render the full symbolic problem, rewritten partial-information problem, candidate query set, and supervision fields 22: Add generated samples to ExtT_Ext 23: end while 24: return ExtT_Ext D.3 GeneReg-MT Gene regulation is fundamental to cellular biological systems. Schematics of gene regulation are usually represented by a network, called Gene Regulatory Networks (GRNs), where nodes represent genes and edges represent how activations of genes affect downstream gene expression. GRNs are often modeled as Boolean networks, which are simple but can yield accurate quantitative results with limited data. Each of the Boolean networks will converge onto a finite set of attractor states, including fixed points (steady states) and limit cycles. These networks provide a testbed to study LLM’s information seeking ability in the natural science domain. In particular, we curate the dataset from [11], which contains 122 Boolean GRNs. We further filter the dataset such that there are 6 to 30 nodes in the graph. For each GRN, based on the number of its fixed points, we consider two goals: (1) Steady-state identification (steady state): Infer which one steady state a partial initial gene expression value assignment will lead to, provided all steady states for this GRN. (2) Steady gene expression identification (marker): Infer which one gene expression value of a specific marker gene a partial initial gene expression value assignment will lead to, provided all steady states for this GRN. A CSP is formalized in this dataset as: • X: Genes in the GRN (values spanning the full Cartesian space) • D: Active,Inactive∀x∈\\Active,Inactive\∀ x \ • A: Partial observation of the initial gene vector • C: Boolean update rules • y: The unique steady state, or a marker gene value at convergence. • S: Some additional gene expressions To create k-underspecified tasks for the former goal, we first obtain sets of gene expression value assignments that will determine the target and cannot be reduced. We then randomly drop k values and brute-force verify whether they form a minimal k-sufficient set. For the latter goal, we exploit its Cartesian variable space and recursively construct k=1,2,3,4k=1,2,3,4-sufficient problems, similar to Logic-Q-MT. In total, we construct 800 problems from 38 GRNs, which induce 2,326 tasks. Example: Gene regulatory network as a CSP. Consider a Boolean gene regulatory network with variables =I,S,M34,Z,M200,X=\I,S,M_34,Z,M_200\, where I denotes the external input, S denotes Snail, M34M_34 denotes miR-34miR-34, Z denotes Zeb, and M200M_200 denotes miR-200miR-200. Each variable is Boolean, so for every Xi∈X_i , i=Active,Inactive,D_i=\Active,Inactive\, or equivalently i=1,0D_i=\1,0\. The constraints C encode the steady-state conditions of the Boolean update rules: S S ←I∧¬(S∧M34), ← I (S M_34), M34 M_34 ←¬S∧¬Z, ← S Z, Z Z ←¬M200∨(S∧Z), ← M_200 (S Z), M200 M_200 ←¬S∨(Z∧M200). ← S (Z M_200). Here each constraint requires the gene value at convergence to agree with its Boolean regulatory rule. The partial observation A specifies known values of some variables, such as an observed or intervened input condition. For example, =I=ActiveA=\I=Active\ restricts the feasible assignments to steady states consistent with an active input. The feasible set is Ω(P)=x∈∏Xi∈i:x⊧ and x⊧. (P)= \x∈ _X_i D_i:x and x \. The target variable Y may be the full steady-state gene expression vector, Y=(S,M34,Z,M200),Y=(S,M_34,Z,M_200), or a marker gene value at convergence, such as Y=ZY=Z. Additional queryable gene expressions are represented by a set ⊆∖dom(),S (A), whose observed values can further restrict Ω(P) (P). For instance, if =I=InactiveA=\I=Inactive\, the constraints imply a unique feasible steady state: Ω(P)=(I=0,S=0,M34=1,Z=0,M200=1). (P)= \(I=0,\ S=0,\ M_34=1,\ Z=0,\ M_200=1) \. Thus the full steady state Y=(S,M34,Z,M200)Y=(S,M_34,Z,M_200) is known. In contrast, if =I=ActiveA=\I=Active\, the feasible steady states are Ω(P)=(I=1,S=1,M34=0,Z=1,M200=0),(I=1,S=1,M34=0,Z=1,M200=1). (P)= \(I=1,\ S=1,\ M_34=0,\ Z=1,\ M_200=0),(I=1,\ S=1,\ M_34=0,\ Z=1,\ M_200=1) \. The full steady-state vector is therefore not uniquely determined, because M200M_200 remains ambiguous. However, a marker target such as Y=ZY=Z is known under A, since all feasible assignments agree that Z=ActiveZ=Active. D.4 ClinGuide-MT D.4.1 ClinGuide-MT problem formulation and construction Clinical guidelines formalize expert knowledge into structured decision procedures for diagnosis and management. They are often organized around presenting symptoms and specify a sequence of conditional decisions that progressively narrow the set of plausible diagnoses, treatments, triage decisions, or follow-up recommendations. This structure makes clinical guidelines a natural source of controlled multi-turn information-seeking tasks: a model must identify which missing clinical evidence is needed, query it in an appropriate order, and stop once the final recommendation is determined. We curate 59 structured diagnostic algorithms spanning 11 clinical areas, including cardiovascular, gastrointestinal, and musculoskeletal conditions, using established clinical textbooks and guidelines as references. Each algorithm is represented as a decision tree. Internal nodes correspond to clinical variables X, such as symptoms, risk factors, medication or substance use, physical-examination findings, laboratory tests, imaging results, or procedure findings. Outgoing edges correspond to possible values of the variable, such as positive or negative test results, acute versus chronic symptom duration, or alternative symptom presentations. Leaf nodes correspond to final outcomes Y, including diagnoses, treatments, triage decisions, or recommended follow-up examinations. Fig. 2 shows a simplified diagnostic algorithm for pelvic pain. The pathway begins with the presenting symptom and proceeds through conditionally relevant variables, such as duration of pain, pregnancy-test result, and laparoscopy finding, before reaching a terminal recommendation. A complete root-to-leaf path therefore defines one diagnostic pathway: an ordered sequence of clinical variable–value pairs together with a final outcome. Pathway validation. The pathways are built upon the diagnostic algorithms in the source textbook [7]. While constructing each problem, every extracted algorithm was manually proofread against the textbook and the journal articles it cites, with particular attention to preserving decision nodes, branches, and terminal recommendations so that each branch leads to a unique outcome; one clinical expert additionally reviewed ten samples of the extracted algorithms and confirmed their fidelity to the source material. To construct multi-turn tasks, we first normalize each diagnostic algorithm only to resolve structural ambiguity, yielding a set of unambiguous root-to-leaf paths. For each leaf node, we backtrack to the root and extract the corresponding ordered pathway. For each k∈1,2,3,4k∈\1,2,3,4\, whenever the path length permits, we mask the final k clinical variables on the path. The unmasked prefix is converted into the observed patient context A, while the masked variables define the minimal sufficient set S whose values are needed to recover the final outcome Y. Full dataset statistics are reported in Appendix Table 11. Each task also includes a query space. The valid query variables are the clinical variables appearing in the corresponding decision tree. To test whether models can identify the correct variables to ask about, we add distractor variables sampled from other ClinGuide-MT problems, excluding variables that overlap with the current tree. These distractors expand the query space but do not affect the ground-truth final outcome. Each resulting task contains: (i) an observed patient context, (i) a set of valid and distractor query variables, (i) the masked order-dependent variables and their ground-truth values, and (iv) the final recommendation as the target outcome. Details of system prompts and oracle prompts are provided in Appendix E.1. The complete formulation of ClinGuide-MT is specified as follows: • X: the set of clinical variables, including symptoms, risk factors, medication or substance use, laboratory tests, imaging results, procedures, and other clinical findings; • D: the domains of the variables in X, specifying their possible values; • A: the observed partial assignment, corresponding to the known patient context provided by the unmasked pathway prefix; • C: the underlying clinical decision structure encoded by the guideline-derived decision tree; • Y: the target outcome, corresponding to the final recommendation, such as a diagnosis, treatment, triage decision, or follow-up action; • S: the masked variables whose values must be queried to determine Y. At evaluation time, the model is given the observed context A and the query space (P)U(P), but not the underlying decision structure C. Thus, ClinGuide-MT tests whether a model can use its implicit clinical knowledge and the available query options to identify the missing variables needed to determine the final recommendation. D.5 20 Questions D.5.1 Problem formulation Each 20Q instance contains a hidden target y, sampled from a finite target set targetY_target. At turn t, the model has observed the interaction history ℋt=(q1,a1),…,(qt−1,at−1),H_t=\(q_1,a_1),…,(q_t-1,a_t-1)\, where qiq_i is the i-th question asked by the model and ai∈yes,no,passa_i∈\ yes, no, pass\ is the examiner’s answer. Given ℋtH_t, the model either asks a new yes-or-no question qtq_t or produces a final guess y y: qt∼πθ(⋅∣ℋt)ory^∼πθ(⋅∣ℋt).q_t _θ(· _t) y _θ(· _t). The goal is to identify the hidden target y within a limited number of turns. The examiner answers each question using an oracle-style function at=g(y,qt),at∈yes,no,pass.a_t=g(y,q_t), a_t∈\ yes, no, pass\. The answer yes means that the question is true for the target; no means that it is false; and pass means that the question is ambiguous, underspecified, only partially true, or cannot be answered cleanly with yes or no. Relation to CSPs. 20Q can be viewed as a generalized underspecified CSP. The hidden target Y is the variable to be determined, and the candidate set provides its finite domain. Each question-answer pair (qt,at)(q_t,a_t) adds a new constraint on feasible target values. After observing ℋtH_t, the remaining feasible targets are those compatible with all previous answers: Ωt=c∈eval:g(c,qi)=aifor all compatible prior turns. _t= \c _eval:g(c,q_i)=a_i\ for all compatible prior turns \. However, unlike our fixed variable-query tasks, the model does not choose from a predefined set of missing variables. The query space is open-ended, and each question defines a new partition of the candidate space. Therefore, the standard notions of a minimal k-sufficient set and a fixed degree of underspecification k are not directly applicable. D.5.2 Candidate-space surrogate In principle, evaluating a question requires knowing how much it narrows the latent space of all possible target values. Because this space is open-ended and difficult to enumerate, we approximate it with a finite candidate set: eval=c1,c2,…,cN.Y_eval=\c_1,c_2,…,c_N\. This candidate set serves as a surrogate hypothesis space for computing question-level and trajectory-level information-seeking metrics. At the beginning of each episode, we initialize a uniform belief over candidates: p0(c)=1|eval|,c∈eval.p_0(c)= 1|Y_eval|, c _eval. The belief distribution is updated turn by turn according to the observed answers. This belief is used only for offline evaluation and is not shown to the model. Candidate pools. We evaluate two main candidate subsets. Common combines common animals, places, foods, and objects. Thing focuses on object-like targets. We also maintain category-level pools for analysis. Table 12 summarizes the target and evaluation candidate sizes. Table 12: Statistics of 20Q candidate pools. The target column reports the number of hidden targets used for evaluation, while the candidate column reports the size of the candidate-space surrogate used for offline question-quality estimation. Pool # Targets |eval||Y_eval| Animals 27 116 Places 21 71 Food 26 92 Objects 37 126 Common 111 405 Thing 200 188 D.5.3 Question-induced partitions For a candidate c∈evalc _eval and a model-generated question qtq_t, the examiner function assigns one of three labels: g(c,qt)∈yes,no,pass.g(c,q_t)∈\ yes, no, pass\. Thus, each question partitions the candidate space into three subsets: yes(qt)=c:g(c,qt)=yes,Y yes(q_t)=\c:g(c,q_t)= yes\, no(qt)=c:g(c,qt)=no,Y no(q_t)=\c:g(c,q_t)= no\, pass(qt)=c:g(c,qt)=pass.Y pass(q_t)=\c:g(c,q_t)= pass\. An informative question should induce a partition that substantially reduces uncertainty about the hidden target under the current belief. For example, broad questions such as whether the target is a living organism may be useful early in the episode, while more specific questions may become useful once the candidate space has been narrowed. D.5.4 Belief update After the model asks qtq_t and receives the observed answer ata_t, we update the belief over candidates using a soft likelihood model. For each candidate c, we define P(at∣c,qt)=α,g(c,qt)=at,β,g(c,qt)=pass,γ,otherwise,P(a_t c,q_t)= casesα,&g(c,q_t)=a_t,\\ β,&g(c,q_t)= pass,\\ γ,&otherwise, cases where we set α=0.98,β=0.50,γ=0.02.α=0.98, β=0.50, γ=0.02. The unnormalized posterior is p~t+1(c)=pt(c)P(at∣c,qt), p_t+1(c)=p_t(c)P(a_t c,q_t), and the normalized posterior is pt+1(c)=p~t+1(c)∑c′∈evalp~t+1(c′).p_t+1(c)= p_t+1(c) _c _eval p_t+1(c ). This update assigns high weight to candidates consistent with the observed answer, low weight to inconsistent candidates, and intermediate weight to candidates for which the question is ambiguous or not cleanly answerable. We use a soft update rather than hard filtering because examiner answers over open-ended natural-language questions can be noisy. The pass response is also not equivalent to contradiction: it indicates ambiguity or insufficient grounding, so candidates in the pass bucket are downweighted less aggressively than candidates with directly inconsistent answers. D.5.5 Evaluation metrics for 20Q We evaluate 20Q at both the instance level and the turn level. Final accuracy measures whether the model identifies the hidden target, while the information-seeking metrics measure whether the questions efficiently reduce uncertainty. Final Accuracy. The primary task-completion metric is whether the final prediction y y matches the hidden target y: Acc=[y^=y].Acc=I[ y=y]. We additionally report the average number of turns used before the model makes its final guess. Entropy. At each turn, we measure the remaining uncertainty over the candidate-space surrogate using Shannon entropy: H(pt)=−∑c∈evalpt(c)logpt(c).H(p_t)=- _c _evalp_t(c) p_t(c). Lower entropy means that the interaction history has narrowed the candidate space more effectively. Expected Information Gain. We quantify how informative a question qtq_t is by its expected reduction in entropy under the current belief, evaluated before the answer is observed. Reusing the soft likelihood P(a∣c,qt)P(a c,q_t) from the belief update, the predictive distribution over the possible answers a∈yes,no,passa∈\ yes, no, pass\ is P(a∣qt)=∑c∈evalpt(c)P¯(a∣c,qt),P¯(a∣c,qt)=P(a∣c,qt)∑a′P(a′∣c,qt),P(a q_t)= _c _evalp_t(c)\, P(a c,q_t), P(a c,q_t)= P(a c,q_t) _a P(a c,q_t), and the hypothetical posterior under a candidate answer a is pt+1(a)(c)=pt(c)P¯(a∣c,qt)∑c′∈evalpt(c′)P¯(a∣c′,qt).p_t+1^(a)(c)= p_t(c)\, P(a c,q_t) _c _evalp_t(c )\, P(a c ,q_t). The expected information gain is the mutual information between the hidden target Y and the as-yet-unobserved answer AtA_t under the current belief: EIG(qt)=H(pt)−∑a∈yes,no,passP(a∣qt)H(pt+1(a))=I(Y;At∣qt).EIG(q_t)=H(p_t)-\!\! _a∈\ yes, no, pass\\!\!P(a q_t)\,H\! (p_t+1^(a) )=I(Y;A_t q_t). A larger value indicates that the question is expected to remove more uncertainty about the hidden target. Unlike the realized reduction H(pt)−H(pt+1)H(p_t)-H(p_t+1), EIGEIG depends only on the current belief and the answer likelihoods induced by the question, and therefore does not require observing the actual answer. Normalized Expected Information Gain. Because later turns naturally have less remaining uncertainty, raw EIGEIG is not directly comparable across turns. We therefore normalize it by the current entropy: nEIG(qt)=EIG(qt)H(pt)+ϵ∈[0,1],nEIG(q_t)= EIG(q_t)H(p_t)+ε∈[0,1], where ϵε is a small constant for numerical stability. This measures the fraction of current uncertainty the question is expected to remove, and is our main per-turn question-informativeness metric. Remaining Entropy Curve. We track H(pt+1)H(p_t+1) across turns to obtain a remaining entropy curve. This curve measures how efficiently the model narrows the candidate space over the interaction. A sharper decrease indicates more efficient information seeking. Pass Mass. For each turn t, after the model asks question qtq_t, we compute the belief mass assigned to candidates for which the question receives a pass label: PassMasst=PassMass(qt)=∑c:g(c,qt)=passpt(c).PassMass_t=PassMass(q_t)= _c:g(c,q_t)= passp_t(c). This is a per-turn metric computed under the current belief ptp_t, before updating the belief with the observed answer ata_t. Thus, pass mass measures how much of the currently plausible candidate space cannot be cleanly partitioned by the question asked at turn t. High pass mass usually indicates that the question is ambiguous, underspecified, difficult to ground, or poorly aligned with the remaining candidate pool. This metric is useful for diagnosing questions that sound plausible but do not cleanly divide the current hypotheses into informative yes and no regions. D.5.6 Offline question-informativeness evaluation The belief update and information-gain metrics are used only for offline analysis and do not affect the interaction protocol seen by the model. During the game, the model observes only the interaction history and the examiner’s answer to each question. After an episode is complete, we replay the trajectory over the candidate-space surrogate and compute per-turn partitions, posterior beliefs, entropy, expected information gain, normalized expected information gain, and pass mass. Unless otherwise specified, we use Qwen3-30B-A3B-Instruct-FP8 to support the offline evaluation. This offline evaluation serves two purposes. First, it separates final task success from question informativeness: a model may guess correctly after asking weak questions, or fail despite asking several informative ones. Second, it enables fine-grained diagnosis of multi-turn information seeking, such as whether a model asks broad high-gain questions early, avoids ambiguous questions, and progressively narrows the candidate space across turns. D.5.7 Human validation of normalized expected information gain nEIG (Appendix D.5.5) measures a narrower property than holistic question informativeness: the reduction of uncertainty under the current belief and the surrogate candidate space. To test whether this quantity tracks human judgments of the same property, we conducted a blinded forced-choice study on 200 interaction states drawn from 111 Common episodes. Protocol. For each sampled state at turn t∈[2,8]t∈[2,8], we paired (i) the question generated by Qwen3-30B-A3B-Thinking-FP8 at that turn with (i) a question generated by GPT-5-mini from the identical truncated history. We excluded identical questions and pairs with |ΔnEIG|<0.01| |<0.01, and retained at most four pairs per episode, separated by at least two turns. A graduate-level annotator saw the candidate pool, the preceding question–answer history, and the two candidate questions in randomized order. The annotator was blinded to the hidden target, the answers to the candidate questions, the model identities, and the nEIGnEIG scores, selected which question would better narrow the remaining possibilities, and rated confidence on a scale from 1 to 3. Results. The higher-nEIGnEIG question matched the human preference in 153 of 200 pairs (76.5%), compared with a 50% chance rate. Agreement was 86.5% for judgments made at the highest confidence level (3), compared with 70.6% and 70.7% at confidence levels 2 and 1, respectively. Table 13 stratifies agreement by the absolute nEIGnEIG difference between the two candidate questions; agreement is significantly above chance in every bin. Table 13: Human–nEIGnEIG agreement stratified by the absolute difference in normalized expected information gain between the two candidate questions. Each cell reports the fraction of pairs in which the higher-nEIGnEIG question matched the blinded annotator’s preference; p-values compare each agreement rate against the chance rate of 0.50.5. |ΔnEIG|| | Human–nEIGnEIG agreement p-value vs. 0.50.5 <0.05<0.05 72.3% <10−4<10^-4 0.050.05–0.100.10 86.5% <10−7<10^-7 0.100.10–0.150.15 81.3% <10−4<10^-4 Scope of the validation. These results provide direct evidence that normalized expected information gain aligns with human judgments of which question better reduces uncertainty over the remaining candidates, particularly when the human preference is expressed with high confidence. They do not imply that the metric reproduces holistic judgments of question informativeness. In particular, nEIGnEIG is defined relative to the surrogate candidate pool, the belief-update procedure, and the offline evaluator described in Appendix D.5.5, and its values inherit the assumptions of these components. Appendix E Prompts and implementation details E.1 Prompt templates Logic-Q-MT. System Prompt (missing variables, k not provided, adapted from [15]) Suppose you know the following rules about Alice: rules_nl You are trying to discern whether a statement about Alice is true given some facts. You have a budget to ask about up to max_k attributes at once. You must decide whether you have enough information to determine whether the final statement is true. You may respond with one of the following: Instructions: 1. If you already have enough information to determine the truth value of the statement, respond strictly with: "End questioning". 2. Otherwise, you MUST select a set of attributes (at least 1 and at most max_k) to query. Choose the best combination that provides the most information regarding the statement. 3. Format the question strictly as: "Question: Is Alice [attribute_1]? Is Alice [attribute_2]? ..." (for at least 1 and at most max_k attributes). 4. Do not output any other text. System Prompt (missing variables, k provided, adapted from [15]) Suppose you know the following rules about Alice: rules_nl You are trying to discern whether a statement about Alice is true given some facts. You must select exactly k attributes of Alice to query in order to gain the most information about the final statement. Instructions: 1. You MUST select exactly k attributes to query. Choose the best combination that provides the most information regarding the statement. 2. Format the question strictly as: "Question: Is Alice [attribute_1]? Is Alice [attribute_2]? ..." (for exactly k attributes). 3. Do not output any other text. System Prompt (degree of underspecification, adapted from [15]) Suppose you know the following rules about Alice: rules_nl You will be given some facts about Alice (some attributes known true/false), and then a target yes/no question of the form "Is Alice X?". Decide whether the target question can be answered with certainty from the given facts and rules. Output in exactly one of these formats: - If the question is NOT ambiguous (it can be answered definitively as Yes or No): "Answer: No" - If the question IS ambiguous because some attribute values are missing: output the MINIMUM number of additional attributes that must be known to answer definitively, as an integer 1-4: "Answer: 1", "Answer: 2", "Answer: 3", or "Answer: 4" - If you are sure it is ambiguous but cannot determine the count: "Answer: Yes, but not sure about how many" Do not output any other text. System Prompt (sequential task-solving, no budget in prompt) Suppose you know the following rules about Alice: rules_nl You are trying to discern whether Alice is goal given some facts. You must decide whether you have enough information to determine whether the final statement is true. At each turn, you may respond with one of the following: Instructions: 1. If you already have enough information to determine the truth value of the statement, respond strictly with: "Answer: goal" or "Answer: not goal". 2. Otherwise, you MUST select exactly one attribute to query. Choose the single attribute that provides the most information regarding the statement, such that the answer can be determined with least questions being asked. 3. Format the question strictly as: "Question: Is Alice [attribute]?" 4. Do not output any other text. IMPORTANT: The initial facts provided are INSUFFICIENT. You MUST ask questions to gather the missing information before you can answer correctly. Do not guess - ask questions first. System Prompt (sequential task-solving, with budget in prompt) Suppose you know the following rules about Alice: rules_nl You are trying to discern whether Alice is goal given some facts. You can take at most max_turns turn(s). In each turn, you may ask about up to max_num_queries_per_turn attribute(s). You must decide whether you have enough information to determine whether the final statement is true. At each turn, you may respond with one of the following: Instructions: 1. If you already have enough information to determine the truth value of the statement, respond strictly with: "Answer: goal" or "Answer: not goal". 2. Otherwise, you MUST select a set of attributes (between 1 and max_num_queries_per_turn) to query. Choose the smallest sufficient combination that provides enough information regarding the statement. 3. Format the question strictly as: "Question: Is Alice [attribute_1]? Is Alice [attribute_2]? ..." (for at least 1 attribute). 4. Do not output any other text. IMPORTANT: The initial facts provided are INSUFFICIENT. You MUST ask questions to gather the missing information before you can answer correctly. Do not guess - ask questions first. User Prompt known_facts known_untrue_facts invalid_qs Is Alice goal? GeneReg-MT. System Prompt (steady state identification, sequential task-solving) You are reasoning about a Boolean gene regulatory network under synchronous updates. You will be given a partial observation of the initial state vector at time t=0, and your task is to identify which attractor ID (fixed point or cycle) the system will reach under synchronous updates starting from that initial state. Instructions: - Genes are binary (0/1). - The update semantics are synchronous (all genes update at the same discrete time step). - Any gene values you ask about are values in the initial state (time t=0). - The final answer refers to the reached attractor (fixed point or cycle). - Respond at each turn with exactly one of: 1) Question: [GENE_NAME] 2) Answer: [ATTRACTOR_ID_INTEGER] Rules: 1. If current information is sufficient, output "Answer: [ATTRACTOR_ID_INTEGER]". 2. Otherwise ask for one gene (or up to the configured max per turn) in format "Question: [GENE_NAME]". 3. Do not output any extra text. IMPORTANT: The current observations are insufficient. Ask questions before answering when uncertain. System Prompt (marker identification, sequential task-solving) You are reasoning about a Boolean gene regulatory network under synchronous updates. You will be given a partial observation of the initial state vector at time t=0, and your task is to identify the value of marker gene marker_gene in the reached attractor (steady behavior under synchronous updates). Instructions: - Genes are binary (0/1). - The update semantics are synchronous (all genes update at the same discrete time step). - Any gene values you ask about are values in the initial state (time t=0). - Respond at each turn with exactly one of: 1) Question: [GENE_NAME] 2) Answer: 0 or Answer: 1 Rules: 1. If current information is sufficient, output "Answer: 0" or "Answer: 1". 2. Otherwise ask for one gene (or up to the configured max per turn) in format "Question: [GENE_NAME]". 3. Do not output any extra text. IMPORTANT: The current observations are insufficient. Ask questions before answering when uncertain. User Prompt (steady state identification, no budget in prompt) Gene index order for all bitstrings below (left->right): gene_index_text Target: determine the attractor ID reached from the true initial state. Synchronous Boolean update rules: rules Attractor catalog (fixed points and cycles) for this model: attractors_catalog Catalog format: - FixedPoint: a single bitstring state. - Cycle: multiple bitstrings joined by " | " (one state after another in the cycle). Currently observed gene values: obs You may NOT ask about these genes: banned User Prompt (marker identification, no budget in prompt) Gene index order for all bitstrings below (left->right): gene_index_text Target: determine converged marker value of marker_gene (0/1). Synchronous Boolean update rules: rules Attractor catalog (fixed points and cycles) for this model: attractors_catalog Catalog format: - FixedPoint: a single bitstring state. - Cycle: multiple bitstrings joined by " | " (one state after another in the cycle). Currently observed gene values: obs You may NOT ask about these genes: banned User Prompt (steady state identification, with budget in prompt) Gene index order for all bitstrings below (left->right): gene_index_text Target: determine the attractor ID reached from the true initial state. You can take up to max_turns turns You may ask about up to max_num_q_per_turn genes per turn Synchronous Boolean update rules: rules Attractor catalog (fixed points and cycles) for this model: attractors_catalog Catalog format: - FixedPoint: a single bitstring state. - Cycle: multiple bitstrings joined by " | " (one state after another in the cycle). Currently observed gene values: obs You may NOT ask about these genes: banned User Prompt (marker identification, with budget in prompt) Gene index order for all bitstrings below (left->right): gene_index_text Target: determine converged marker value of marker_gene (0/1). You can take up to max_turns turns You may ask about up to max_num_q_per_turn genes per turn Synchronous Boolean update rules: rules Attractor catalog (fixed points and cycles) for this model: attractors_catalog Catalog format: - FixedPoint: a single bitstring state. - Cycle: multiple bitstrings joined by " | " (one state after another in the cycle). Currently observed gene values: obs You may NOT ask about these genes: banned GSME-Q-MT and GSME-Q-MT-Ext. System Prompt (sequential task-solving) You are solving a math problem. You must decide whether you have enough information to solve this problem. Rules: 1) You may ask only about leaf variables (given as candidates). 2) You must NOT ask about the goal variable. 3) You must NOT ask about any non-leaf variable. 4) If you ask an invalid variable, the user will refuse and you must ask again. When asking, use one of these formats: - "Question: What is VAR?" - "Questions: VAR1, VAR2, ..." When answering, use: - "Answer: <number>" (raw number only) Do not output other formats. You may ask at most ONE variable per turn. Use fewer turns when possible. User Prompt Math problem: problem ClinGuide-MT. System Prompt (Model, sequential task-solving) You are a clinical decision support system. You may only ask questions from the following. Allowed questions: allowed questions Possible recommendations: all recommendations Instructions: You will be given an initial patient presentation and may ask up to budget follow-up questions over multiple turns. Your goal is to select the correct recommendation from possible recommendations. At each turn: - If you have enough information to determine a single recommendation, respond strictly with: "Answer: [recommendation]". - Otherwise, ask exactly one question to obtain the most critical missing information. Respond strictly with: "Question: [question]?" - You may only ask questions that relate to the allowed questions above. Do not ask about topics not listed. Question selection strategy: Not all allowed topics may be equally informative for this patient. At each turn, choose the single question whose answer is most likely to distinguish among the possible recommendations above, allowing you to reach the correct recommendation in the fewest total questions. Note: Some of the allowed question topics are drawn from other clinical guidelines and are distractors — they are not relevant to the possible recommendations for this patient. Before asking, critically assess whether each topic can actually distinguish among the recommendations listed above. Skip topics that cannot. User Prompt (Model, sequential task-solving) You are presented a patient with the following information: Initial patient context + oracle history What question/recommendation should you ask/give to the patient? System Prompt (Oracle, sequential task-solving) You are an oracle that answers clinical questions about a patient based ONLY on provided information. You will receive: 1. A list of desired question-answer pairs about the patient. The desired question might be a summary or concept that is desirable to be asked about, but not an actual question. 2. One or more questions to answer For each question you must: 1. Try to match it with one of the desired questions (allow paraphrasing, e.g., "patient’s age" matches "age of the patient", "is the patient pregnant" matches "pregnancy test", etc.) 2. If matched, output the corresponding answer from the desired pairs 3. If no match exists, output "Not sure" Critical rules: - Only answer based on the provided question-answer pairs - Do not make up or infer any information - If a question cannot be matched to a desired question, you must output "Not sure" - Allow matching for questions that are paraphrased but semantically equivalent - The past Q&A history is provided only for context/reference - do not exclude any options based on what was previously answered - Even if a question was asked before, you should still match and answer it normally User Prompt (Oracle, sequential task-solving) Desired question-answer pairs about this patient: desired pairs textpast history text Questions to answer: questions text 20Q. System Prompt (Guesser, sequential task-solving) Let us play the game of 20 questions. I am impersonating the thing, X. Your goal is to identify X within at most 20 turns. Rules: 1. Ask exactly one question only. 2. Each question should start with "Is X" whenever possible. 3. Do not ask more than one question in a turn. 4. Do not add explanation, justification, or extra text. 5. If this is the final turn, do not ask a question. Instead, make exactly one final guess. Final-turn output rule: - On the final turn, output only: X is "<your best guess>". Let us begin. Ask me the first question. Reply with exactly one action only. Allowed actions: 1. one yes/no question, or 2. one direct guess of X. Do not output multiple questions. Do not output both a question and a guess. Keep the reply short. System Prompt (Examiner, sequential task-solving) Let us play the game of 20 questions. You are the answerer and I am the guesser. X is item. You must answer each question truthfully based on being X, but you must follow this output rule strictly: Allowed responses: - "Yes" - "No" - "Partially" - "Not applicable" - "You guessed it. X is item." Important rules: 1. Output exactly one of the allowed responses above. 2. Do not add any explanation, justification, hint, clarification, punctuation, or extra words. 3. Do not reveal any additional information about X beyond the allowed response. 4. If the guess is exactly correct, output: "You guessed it. X is item." 5. For all other questions, output only one of: "Yes", "No", "Partially", or "Not applicable". Examples of forbidden outputs: - "Yes, because it is a mammal." - "No. It usually lives in Africa." - "Partially, since that depends on context." Examples of valid outputs: - "Yes" - "No" - "Partially" - "Not applicable" Let us begin. Here is my first question. System Prompt (Offline Evaluator, sequential task-solving) You are a strict oracle used inside a 20-questions benchmark. You will be given one yes/no style question about X and a numbered list of candidate entities. For each candidate, answer what the truthful response would be IF X were exactly that candidate. Allowed labels: - Yes - No - Pass Use Pass when the question is ambiguous, malformed, underspecified, only partially true, context-dependent, or cannot be answered cleanly with a definite Yes or No. Output format requirements: Return exactly one line per candidate. Each line must be exactly: <index>. <Yes|No|Pass> Examples: 1. Yes 2. No 3. Pass Do not include candidate names. Do not include explanations. Do not omit any candidate. Do not add any extra text before or after the answer list. User Prompt (Offline Evaluator, sequential task-solving) Candidate: candidate Question: question Return exactly one token: Yes / No / Pass E.2 Experiment compute resources All open-weight models are served locally with vLLM behind an OpenAI-compatible endpoint and queried by our multi-turn evaluator through that endpoint. Each evaluation job launches a dedicated vLLM server in a containerized environment on a dynamically-selected free port; the evaluator only begins after both a liveness check and a model-readiness check succeed. Closed-API models are queried through their respective provider APIs using the same evaluator. Open-weight inference uses H100 GPUs. Tensor parallelism is set per model size: TP=4=4 for Qwen3.5-122B-A10B-FP8, TP=2=2 for Qwen3-Next-80B-A3B-Thinking-FP8, and TP=1=1 for all other open-weight models in our study (Qwen3.5-4B, 9B, 27B-FP8, 35B-A3B-FP8, Qwen3-4B-Thinking-2507, Qwen3-30B-A3B-Thinking-2507-FP8, and gpt-oss-20B, 120B). Across all servers we use a maximum context length of 131,072131,072 tokens, an FP8 KV cache where supported, chunked prefill, asynchronous scheduling, and disable multimodal inputs and prefix caching for consistency. GPU memory utilization is set to 0.950.95 for single-GPU servers and 0.900.90 for tensor-parallel servers. Per-model batching parameters (max-num-batched-tokens, max-num-seqs) and evaluator concurrency are tuned to saturate the server without exceeding its sequence cap. For gpt-oss models we set the reasoning effort to medium or high as indicated in the corresponding results; reasoning-parser settings follow the model family defaults. Appendix F Benchmarking results We benchmark LLMs’ performance in multi-turn information seeking. Open-weight models are hosted locally on Nvidia H100 GPUs and run with vLLM. Proprietary models are run through APIs with default inference parameters recommended by the respective providers. Logic-Q-MT, GeneReg-MT, GSME-Q-MT, GSME-Q-MT-ext. As noted in the main Results, we treat final sufficiency as a key metric for evaluating which variables a model queries with these datasets. We found that models exhibit varying performances, with some models (such as GPT-5 and GPT-5-mini) capable of querying all required information in almost all cases in Logic-Q-MT and in many cases in GeneReg-MT, while some usually failing to query sufficiently (Figs. 15,16,17; full results in Tables 14, 15). Again, although we did not include any information about the degree of underspecification in prompt, LLMs generally perform worse in tasks with higher k’s. ClinGuide-MT. Results are shown in Table 17. 20-Questions. Results are shown in Table 18. Figure 15: Performance and turns used of LLMs in Logic-Q-MT task-solving. Note that the proportion of interactions with final sufficiency = 1 is equal to the proportions that finish on sufficient turn (green) and that finish after sufficient turn (light green). LLMs are ordered by final sufficiency for k=3k=3 tasks. “Random” randomly selects a variable that has not been queried from the valid variables per turn. Figure 16: Performance and turns used of LLMs in GeneReg-MT dynamic steady-state task-solving. Similar to Fig. 15 the proportion of samples with final sufficiency = 1 is equal to the proportions that finish on sufficient turn (green) and that finish after sufficient turn (light green). The high performance of random baseline is due to the low number of valid variables per task. LLMs are ordered by final sufficiency for k=4k=4 tasks. We do not include a random baseline as there are fewer than 10 valid variables in many tasks, which naturally leads to near-perfect performance of random baselines. Figure 17: Performance and turns used of LLMs in GeneReg-MT dynamic marker task-solving. Similar to Fig. 15 the proportion of samples with final sufficiency = 1 is equal to the proportions that finish on sufficient turn (green) and that finish after sufficient turn (light green). The high performance of random baseline is due to the low number of valid variables per task. More concretely, for k=1,2,3,4k=1,2,3,4, there are 86/100, 86/100, 84/100, 84/100 tasks with 10 or fewer valid variables, respectively, to query for. Some “final sufficiency turn” values are missing in the lower panel, because there is no final sufficient interaction for that model and that k. LLMs are ordered by final sufficiency for k=4k=4 tasks. We do not include a random baseline as there are fewer than 10 valid variables in many tasks, which naturally leads to near-perfect performance of random baselines. Table 14: Logic-Q-MT results across different underspecification levels k. Suff. denotes final sufficiency, Acc. denotes answer accuracy, Turn denotes the average number of turns, and OverQ denotes over-questioning rate. Gemini-3.1-Pro is evaluated on a reduced set of conditions and is therefore excluded from the cross-model analyses reported in the main text. Model = k=1 = k=2 = k=3 Suff. ↑ Acc. ↑ Turn OverQ ↓ Suff. ↑ Acc. ↑ Turn OverQ ↓ Suff. ↑ Acc. ↑ Turn OverQ ↓ GPT-5 1.000 1.000 2.128 0.585 0.975 0.988 3.870 0.785 0.955 0.973 4.720 0.815 GPT-5-mini 0.983 0.990 3.488 0.715 0.908 0.938 4.628 0.785 0.858 0.935 5.530 0.790 Gemini-3-Flash 0.945 0.970 1.303 0.213 0.603 0.808 2.275 0.293 0.405 0.675 2.815 0.270 Qwen3-4B-Thinking 0.788 0.858 2.813 0.555 0.668 0.815 4.265 0.578 0.560 0.710 4.725 0.470 Qwen3.5-9B 0.890 0.913 2.355 0.558 0.840 0.880 3.790 0.680 0.750 0.843 4.508 0.660 Qwen3.5-27B-FP8 0.805 0.898 2.055 0.523 0.795 0.900 3.630 0.670 0.713 0.843 4.408 0.658 Qwen3-30B-A3B-Thinking-FP8 0.710 0.840 2.750 0.515 0.490 0.743 3.545 0.420 0.275 0.618 3.743 0.233 Qwen3.5-35B-A3B-FP8 0.868 0.945 2.030 0.518 0.815 0.905 3.418 0.650 0.720 0.863 4.245 0.608 Qwen3-Next-80B-A3B-Thinking-FP8 0.390 0.440 1.708 0.253 0.248 0.288 2.300 0.208 0.173 0.283 2.588 0.153 Qwen3.5-122B-A10B-FP8 0.968 0.975 2.720 0.695 0.843 0.925 3.868 0.685 0.758 0.875 4.735 0.668 gpt-oss-20B-medium 0.750 0.830 4.263 0.608 0.575 0.745 5.503 0.520 0.505 0.695 5.948 0.460 gpt-oss-20B-high 0.935 0.933 4.110 0.710 0.840 0.908 5.490 0.720 0.818 0.900 6.470 0.733 gpt-oss-120B-medium 0.913 0.963 3.610 0.713 0.795 0.903 4.778 0.695 0.688 0.838 5.465 0.655 gpt-oss-120B-high 0.978 0.983 2.635 0.680 0.940 0.975 4.308 0.815 0.903 0.953 5.103 0.815 Gemini-3.1-Pro 0.923 0.960 1.775 0.393 0.610 0.808 2.888 0.435 0.380 0.698 3.168 0.290 Table 15: GeneReg-MT results. Suff. denotes final sufficiency, Acc. denotes answer accuracy, # Turn denotes the average number of turns, and OverQ denotes over-questioning rate. Gemini-3.1-Pro is evaluated on a reduced set of conditions and is therefore excluded from the cross-model analyses reported in the main text. Model k Steady state Marker Suff. ↑ Acc. ↑ # Turn OverQ ↓ Suff. ↑ Acc. ↑ # Turn OverQ ↓ GPT-5 k=1k=1 0.956 0.964 1.004 0.036 0.895 0.925 0.925 0.020 k=2k=2 0.887 0.927 1.981 0.063 0.760 0.865 1.765 0.040 k=3k=3 0.802 0.849 2.960 0.079 0.600 0.820 2.330 0.065 k=4k=4 0.628 0.769 3.431 0.081 0.515 0.790 2.860 0.045 GPT-5-mini k=1k=1 0.861 0.916 1.159 0.227 0.815 0.895 1.065 0.135 k=2k=2 0.716 0.770 2.136 0.230 0.515 0.735 1.520 0.065 k=3k=3 0.575 0.671 2.705 0.204 0.375 0.715 1.910 0.060 k=4k=4 0.388 0.544 3.391 0.156 0.335 0.650 2.285 0.065 Gemini-3-Flash k=1k=1 0.729 0.833 0.781 0.028 0.750 0.875 0.775 0.005 k=2k=2 0.423 0.599 1.134 0.028 0.490 0.765 1.340 0.040 k=3k=3 0.238 0.440 1.295 0.025 0.295 0.675 1.520 0.015 k=4k=4 0.106 0.359 1.194 0.019 0.225 0.585 1.845 0.020 Qwen3-4B-Thinking k=1k=1 0.693 0.546 2.120 0.434 0.325 0.625 1.125 0.040 k=2k=2 0.275 0.364 1.934 0.181 0.090 0.535 1.110 0.050 k=3k=3 0.166 0.261 2.325 0.125 0.010 0.530 1.040 0.000 k=4k=4 0.103 0.222 2.369 0.078 0.025 0.550 1.185 0.000 Qwen3.5-9B k=1k=1 0.594 0.693 1.235 0.279 0.540 0.760 0.915 0.170 k=2k=2 0.486 0.538 2.202 0.324 0.160 0.570 0.875 0.075 k=3k=3 0.321 0.406 2.541 0.217 0.075 0.470 0.820 0.025 k=4k=4 0.169 0.266 2.622 0.109 0.060 0.530 1.140 0.010 Qwen3.5-27B-FP8 k=1k=1 0.773 0.821 1.649 0.382 0.690 0.795 0.995 0.130 k=2k=2 0.580 0.627 2.331 0.298 0.285 0.615 1.260 0.080 k=3k=3 0.361 0.490 2.645 0.214 0.085 0.570 1.225 0.020 k=4k=4 0.191 0.338 2.934 0.128 0.055 0.505 1.355 0.015 Qwen3-30B-A3B-Thinking-FP8 k=1k=1 0.629 0.729 1.402 0.263 0.445 0.700 0.880 0.110 k=2k=2 0.390 0.507 2.066 0.251 0.205 0.565 0.940 0.050 k=3k=3 0.246 0.399 2.217 0.142 0.055 0.550 0.705 0.020 k=4k=4 0.200 0.319 2.584 0.103 0.045 0.520 0.900 0.005 Qwen3-Next-80B-A3B-Thinking-FP8 k=1k=1 0.562 0.438 1.203 0.215 0.385 0.595 0.835 0.110 k=2k=2 0.279 0.305 1.512 0.141 0.090 0.550 0.595 0.010 k=3k=3 0.157 0.231 1.696 0.093 0.005 0.460 0.545 0.000 k=4k=4 0.094 0.184 1.856 0.063 0.005 0.515 0.695 0.000 gpt-oss-20B-medium k=1k=1 0.546 0.681 1.219 0.287 0.410 0.655 1.015 0.165 k=2k=2 0.401 0.523 2.056 0.263 0.140 0.540 0.850 0.070 k=3k=3 0.219 0.408 2.471 0.168 0.090 0.555 1.225 0.060 k=4k=4 0.072 0.250 2.141 0.059 0.035 0.500 1.125 0.010 gpt-oss-20B-high k=1k=1 0.590 0.705 1.323 0.315 0.390 0.635 0.945 0.175 k=2k=2 0.394 0.523 2.073 0.293 0.155 0.535 1.040 0.100 k=3k=3 0.206 0.403 2.353 0.168 0.075 0.525 0.990 0.050 k=4k=4 0.078 0.238 2.194 0.047 0.020 0.565 1.015 0.005 gpt-oss-120B-medium k=1k=1 0.709 0.805 0.920 0.124 0.540 0.725 0.705 0.045 k=2k=2 0.528 0.669 1.613 0.110 0.195 0.620 0.925 0.035 k=3k=3 0.335 0.514 2.025 0.098 0.065 0.530 0.870 0.000 k=4k=4 0.175 0.344 1.991 0.044 0.030 0.470 0.805 0.000 gpt-oss-120B-high k=1k=1 0.729 0.841 0.948 0.135 0.580 0.765 0.710 0.040 k=2k=2 0.519 0.627 1.500 0.092 0.230 0.590 0.925 0.040 k=3k=3 0.342 0.507 2.083 0.113 0.065 0.600 0.850 0.005 k=4k=4 0.156 0.406 1.941 0.038 0.045 0.505 0.945 0.005 Gemini-3.1-Pro k=1k=1 0.992 0.984 1.060 0.056 0.940 0.975 1.015 0.020 k=2k=2 0.965 0.969 2.127 0.080 0.960 0.970 2.140 0.130 k=3k=3 0.883 0.928 3.095 0.081 0.955 0.975 3.080 0.180 k=4k=4 0.906 0.941 4.038 0.178 0.905 0.960 3.925 0.155 Qwen3.5-122B-A10B-FP8 k=1k=1 0.825 0.817 2.506 0.570 0.730 0.840 1.070 0.115 k=2k=2 0.634 0.615 3.265 0.472 0.250 0.605 1.300 0.100 k=3k=3 0.431 0.480 3.635 0.342 0.110 0.575 1.310 0.050 k=4k=4 0.250 0.341 3.678 0.203 0.060 0.540 1.465 0.010 Qwen3.5-35B-A3B-FP8 k=1k=1 0.693 0.681 1.259 0.227 0.605 0.755 0.745 0.040 k=2k=2 0.329 0.444 1.793 0.176 0.110 0.565 0.830 0.020 k=3k=3 0.174 0.316 2.002 0.125 0.020 0.490 0.725 0.000 k=4k=4 0.084 0.244 2.191 0.063 0.000 0.485 0.825 0.000 Qwen3.5-4B k=1k=1 0.502 0.594 1.068 0.195 0.390 0.670 0.755 0.085 k=2k=2 0.272 0.394 1.509 0.150 0.090 0.510 0.670 0.020 k=3k=3 0.147 0.278 1.669 0.091 0.025 0.510 0.555 0.000 k=4k=4 0.084 0.209 1.900 0.075 0.020 0.590 0.820 0.005 Table 16: GSME-Q-MT and its extension results. Suff. denotes final sufficiency, Acc. denotes answer accuracy, # Turn denotes the average number of turns, and OverQ denotes over-questioning rate. Model k GSME-Q-MT GSME-Q-MT-Ext Suff. ↑ Acc. ↑ # Turn OverQ ↓ Suff. ↑ Acc. ↑ # Turn OverQ ↓ Qwen3-4B-Thinking k=1k=1 0.989 0.988 0.99±0.120.99±0.12 0.004 0.813 0.813 0.84±0.420.84±0.42 0.030 k=2k=2 0.986 0.985 1.97±0.221.97±0.22 0.001 0.681 0.639 1.42±0.891.42±0.89 0.028 k=3k=3 0.983 0.985 2.95±0.372.95±0.37 0.001 0.585 0.520 1.78±1.371.78±1.37 0.008 k=4k=4 0.981 0.980 3.93±0.533.93±0.53 0.001 0.417 0.342 1.76±1.761.76±1.76 0.024 Qwen3-30B-A3B-Thinking-FP8 k=1k=1 0.985 0.984 0.99±0.120.99±0.12 0.004 0.463 0.485 0.46±0.500.46±0.50 0.000 k=2k=2 0.981 0.974 1.96±0.241.96±0.24 0.001 0.368 0.319 0.74±0.910.74±0.91 0.004 k=3k=3 0.985 0.980 2.96±0.292.96±0.29 0.000 0.258 0.211 0.79±1.230.79±1.23 0.005 k=4k=4 0.981 0.973 3.92±0.463.92±0.46 0.000 0.264 0.195 1.09±1.551.09±1.55 0.008 gpt-oss-20B-medium k=1k=1 0.993 0.988 0.99±0.090.99±0.09 0.001 0.948 0.933 0.96±0.230.96±0.23 0.015 k=2k=2 0.871 0.838 1.74±0.621.74±0.62 0.000 0.941 0.896 1.89±0.381.89±0.38 0.004 k=3k=3 0.780 0.697 2.34±1.082.34±1.08 0.001 0.911 0.837 2.75±0.672.75±0.67 0.005 k=4k=4 0.693 0.564 2.77±1.552.77±1.55 0.000 0.821 0.724 3.33±1.243.33±1.24 0.010 gpt-oss-120B-medium k=1k=1 0.999 0.998 1.00±0.031.00±0.03 0.000 1.000 1.000 1.00±0.001.00±0.00 0.000 k=2k=2 0.990 0.983 1.98±0.151.98±0.15 0.001 0.993 0.993 1.99±0.171.99±0.17 0.000 k=3k=3 0.860 0.718 2.58±0.722.58±0.72 0.000 0.986 0.984 2.96±0.322.96±0.32 0.000 k=4k=4 0.601 0.318 2.40±1.172.40±1.17 0.000 0.882 0.813 3.53±1.003.53±1.00 0.000 GPT-5-mini k=1k=1 1.000 0.998 1.00±0.041.00±0.04 0.002 1.000 1.000 1.00±0.001.00±0.00 0.000 k=2k=2 0.998 0.998 2.00±0.062.00±0.06 0.001 1.000 1.000 2.01±0.082.01±0.08 0.004 k=3k=3 0.999 0.999 3.00±0.063.00±0.06 0.000 1.000 1.000 3.00±0.003.00±0.00 0.000 k=4k=4 0.998 0.997 3.99±0.133.99±0.13 0.000 1.000 1.000 4.00±0.004.00±0.00 0.000 Gemini-3-Flash k=1k=1 0.999 0.996 1.00±0.071.00±0.07 0.004 1.000 1.000 1.01±0.091.01±0.09 0.008 k=2k=2 0.995 0.993 1.99±0.121.99±0.12 0.002 0.993 0.993 1.99±0.191.99±0.19 0.004 k=3k=3 0.990 0.982 2.98±0.262.98±0.26 0.002 0.989 0.984 2.97±0.282.97±0.28 0.000 k=4k=4 0.980 0.960 3.93±0.423.93±0.42 0.003 0.988 0.984 3.96±0.393.96±0.39 0.002 Table 17: ClinGuide-MT results. “d” represents the set of distractor variables added in each problem, all obtained from other ClinGuide-MT problems and filtered. #d refers to the number of distracting variable sets. Model k Final acc. ↑ Order correctness ↑ Query correctness ↑ Query coverage ↑ Avg. turn used #d=0 #d=10 #d=20 #d=0 #d=10 #d=20 #d=0 #d=10 #d=20 #d=0 #d=10 #d=20 #d=0 #d=10 #d=20 Qwen3-4B-Thinking k=1k=1 0.503 0.436 0.426 0.916 0.739 0.749 0.575 0.384 0.384 0.916 0.739 0.749 3.084 5.269 5.284 k=2k=2 0.461 0.350 0.333 0.917 0.874 0.883 0.700 0.493 0.514 0.743 0.618 0.594 3.249 5.159 5.145 k=3k=3 0.414 0.322 0.276 0.857 0.892 0.873 0.785 0.618 0.619 0.701 0.572 0.558 3.538 4.754 4.905 k=4k=4 0.339 0.317 0.304 0.779 0.819 0.858 0.828 0.674 0.684 0.681 0.532 0.531 3.868 4.894 4.758 Qwen3-30B-A3B-Thinking-FP8 k=1k=1 0.560 0.486 0.451 0.783 0.616 0.601 0.546 0.409 0.397 0.783 0.616 0.601 2.296 2.987 2.950 k=2k=2 0.543 0.396 0.428 0.910 0.828 0.801 0.735 0.597 0.560 0.693 0.572 0.547 2.650 3.344 3.423 k=3k=3 0.495 0.381 0.386 0.850 0.836 0.830 0.793 0.708 0.673 0.662 0.542 0.545 3.162 3.459 3.551 k=4k=4 0.396 0.339 0.322 0.840 0.838 0.859 0.839 0.750 0.736 0.597 0.536 0.518 3.401 3.797 3.828 Qwen3.5-27B-FP8 k=1k=1 0.749 0.714 0.712 0.948 0.906 0.906 0.578 0.447 0.454 0.948 0.906 0.906 3.203 4.781 4.987 k=2k=2 0.686 0.692 0.665 0.915 0.895 0.892 0.712 0.563 0.570 0.873 0.856 0.843 3.849 5.568 5.704 k=3k=3 0.689 0.622 0.632 0.812 0.805 0.805 0.755 0.641 0.630 0.852 0.813 0.824 4.597 6.346 6.392 k=4k=4 0.652 0.626 0.617 0.715 0.702 0.729 0.809 0.704 0.689 0.855 0.814 0.790 5.317 6.943 6.767 GPT-5-mini k=1k=1 0.720 0.666 0.687 0.929 0.839 0.852 0.646 0.497 0.494 0.929 0.839 0.852 3.269 3.793 3.779 k=2k=2 0.646 0.591 0.610 0.928 0.912 0.912 0.729 0.619 0.629 0.782 0.752 0.710 3.715 4.373 4.260 k=3k=3 0.584 0.557 0.568 0.851 0.856 0.854 0.798 0.694 0.707 0.734 0.691 0.688 4.092 4.719 4.700 k=4k=4 0.568 0.546 0.533 0.787 0.814 0.796 0.832 0.768 0.750 0.725 0.665 0.676 4.674 5.123 5.233 GPT-5 k=1k=1 0.793 0.745 0.739 0.935 0.881 0.875 0.668 0.584 0.557 0.935 0.881 0.875 2.461 2.779 2.841 k=2k=2 0.748 0.721 0.704 0.930 0.921 0.936 0.778 0.709 0.706 0.848 0.838 0.812 3.298 3.753 3.694 k=3k=3 0.727 0.673 0.657 0.867 0.853 0.846 0.822 0.768 0.749 0.814 0.786 0.776 3.997 4.454 4.500 k=4k=4 0.696 0.656 0.656 0.782 0.775 0.801 0.849 0.803 0.802 0.807 0.789 0.773 4.749 5.295 5.269 gpt-oss-20B-medium k=1k=1 0.436 0.390 0.365 0.810 0.637 0.645 0.453 0.342 0.357 0.810 0.637 0.645 4.656 4.935 5.265 k=2k=2 0.396 0.331 0.323 0.893 0.813 0.807 0.653 0.492 0.487 0.748 0.615 0.596 4.727 5.767 5.671 k=3k=3 0.359 0.281 0.295 0.827 0.787 0.813 0.688 0.574 0.565 0.708 0.582 0.607 5.249 5.703 6.065 k=4k=4 0.366 0.295 0.251 0.730 0.767 0.741 0.742 0.634 0.619 0.693 0.595 0.602 5.476 6.463 6.696 Gemini-3-Flash k=1k=1 0.866 0.856 0.841 0.979 0.987 0.985 0.728 0.673 0.638 0.979 0.987 0.985 2.230 2.885 2.891 k=2k=2 0.813 0.834 0.822 0.938 0.931 0.930 0.793 0.743 0.735 0.889 0.914 0.898 3.086 3.690 3.537 k=3k=3 0.824 0.778 0.814 0.854 0.841 0.838 0.846 0.797 0.789 0.857 0.874 0.873 3.786 4.370 4.400 k=4k=4 0.793 0.775 0.784 0.757 0.743 0.736 0.872 0.816 0.823 0.852 0.836 0.840 4.722 5.115 5.079 Table 18: 20 Questions results on Common and Things domains. Examiner Guesser Common Things Acc. ↑ #avg turns avg. norm IG ↑ avg. final H ↓ Acc. ↑ #avg turns avg. norm IG ↑ avg. final H ↓ GPT-5-mini gpt-oss-20B-medium 0.1712 18.7928 0.1563 1.7203 0.1100 19.3550 0.1644 1.6599 Qwen3-4B-Thinking 0.2252 18.6847 0.1557 1.6206 0.1350 19.1400 0.1561 1.6941 Qwen3-30B-A3B-Thinking-FP8 0.2793 18.0000 0.1673 1.7864 0.2650 18.0950 0.1607 1.8684 Gemini-3-Flash 0.4775 16.2883 0.1768 1.2130 0.3300 17.5550 0.2050 1.3496 GPT-5-mini 0.4234 17.1982 0.2030 1.4651 0.3800 17.5900 0.1829 1.6172 GPT-5 0.5405 17.0270 0.2047 1.3696 0.4200 17.7200 0.2221 1.3044 Qwen3-30B-A3B-Instruct-FP8 gpt-oss-20B-medium 0.2072 18.8288 0.1779 1.6254 0.1450 19.0800 0.1815 1.5974 Qwen3-4B-Thinking 0.2072 18.8739 0.1692 1.7097 0.2100 18.7550 0.1973 1.5362 Qwen3-30B-A3B-Thinking-FP8 0.2703 18.2703 0.1535 1.7776 0.2600 17.9300 0.1545 1.7649 Gemini-3-Flash 0.4595 16.7207 0.1681 1.5350 0.3000 17.9350 0.1994 1.4787 GPT-5-mini 0.3964 17.4234 0.2249 1.3660 0.3300 17.8650 0.2488 1.4678 GPT-5 0.3964 17.4775 0.2111 1.1027 0.3400 18.0150 0.2398 1.1745 Appendix G Additional results and experiments G.1 Logic-Q-MT and GeneReg-MT G.1.1 Details on first-turn CoT analysis The unit of analysis is a interaction with at least one interaction turn. We study two outcomes: Final sufficiency and second-turn hit (whether the second query is in the MSS, restricted to interactions whose first query misses the MSS and that continue to the second turn). Interactions with no strict query-context variable mention are retained and assigned MSS relative mention rate Ri=0R_i=0. Feature extraction. Let MiM_i denote the MSS for interaction i, and let QiQ_i denote the set of queryable variables. We first detect variables that appear in strict query-planning contexts using the deterministic templates in Table 19. We count a variable as appearing in a query-planning context only when it occurs in text explaining what information the model needs, intends to ask for, or considers useful for disambiguating the target. Mentions copied from the problem statement or appearing only in unrelated reasoning are not counted. The strict query-planning templates are intentionally conservative. Annotated examples in Appendix G.1.2 illustrate the distinction between awareness and MSS-focused planning. The primary feature is Ri=|v∈Mi:v is mentioned in a strict query-planning context||v∈Qi:v is mentioned in a strict query-planning context|,R_i= |\v∈ M_i:v is mentioned in a strict query-planning context\||\v∈ Q_i:v is mentioned in a strict query-planning context\|, (1) with Ri=0R_i=0 when the denominator is zero. We refer to RiR_i as MSS relative mention rate. As a contrastive feature, we also extract awareness of underspecification, a binary indicator for generic statements that more information is still needed, without naming a specific variable. Dataset Construct Feature Templates used Logic-Q-MT Knows what is missing MSS relative mention rate ask about var, ask is alice var, ask if alice is var, ask whether alice is var, ask if she is var, ask whether she is var, consider querying var, should ask about var, should ask if alice is var, should ask whether alice is var, need to ask about var, need to ask if alice is var, need to ask whether alice is var, if i ask var, if i ask about var, if i ask is alice var, if i ask if alice is var, if we ask var, if we ask about var, if we ask is alice var, if we ask if alice is var, next question is var, next question is is alice var, question is alice var, question is is alice var, question should be var, question should be is alice var, question would be var, question would be is alice var, best question is var, best question is is alice var, best question would be var, best question would be is alice var, choose var as the next question, choose asking whether alice is var, choose to ask whether alice is var, need to know var, need to know whether alice is var GeneReg-MT Knows what is missing MSS relative mention rate ask about var, ask var, ask for var, ask for the value of var, ask the value of var, should ask about var, should ask var, should ask for var, need to ask about var, need to ask var, need to ask for var, next question is var, next question should be var, next question var, question should be var, best question is var, want to ask about var, want to ask var, let me ask var, let me ask about var, lets ask var, lets ask about var, go with var, going with var, choose var, choosing var, choose to ask var, choose to query var, query var, query about var, query the value of var, should query var, need to query var Both datasets Knows something is missing Awareness of underspecification need more information, need more info, need more facts, need another question, need additional information, need additional facts, more information is needed, more info is needed, more facts are needed, more information is required, more facts are required, dont have enough information, do not have enough information, dont have enough info, do not have enough info, dont have enough facts, do not have enough facts, this is ambiguous, the situation is ambiguous, not yet enough, not yet sufficient, not yet determined, cannot yet determine, cannot yet conclude, cannot yet answer, can not yet determine, can not yet conclude, cant yet determine, cant yet conclude, still need to ask, still need to check, still need to determine, still need to find out, need to ask one more, need to ask another Table 19: Pattern templates used in the first-turn CoT analysis. The GeneReg-MT query-planning templates are intentionally narrower than the Logic-Q-MT templates to reduce false positives from regulatory-rule enumeration. Additional controls. The first-turn CoT controls are first-turn CoT length, first-turn chosen-query mention, and variable search breadth. The problem-difficulty controls are: • Logic-Q-MT: # rules, mean rule size, problem depth, # queryable variables, || , and fraction of rules with MSS variables. • GeneReg-MT: # regulatory edges, dynamics depth, # queryable variables, || , and fraction of total regulatory in-edges into MSS genes. Pooled fixed-effect models. For Logic-Q-MT, the pooled model is logitPr(Yi=1)=αm(i)+γk(i)+βRRi+βAAi+i⊤,logit (Y_i=1)= _m(i)+ _k(i)+ _RR_i+ _AA_i+x_i θ, where αm(i) _m(i) are model fixed effects, γk(i) _k(i) are underspecification-level fixed effects, AiA_i is awareness of underspecification, and ix_i contains the remaining CoT and problem controls. Standard errors are clustered by interaction. For GeneReg-MT we use the same specification separately within each subset s∈steady state, markers∈\steady state, marker\, logitPr(Yi=1∣s(i)=s)=αm(i)(s)+γk(i)(s)+βR(s)Ri+βA(s)Ai+i⊤(s),logit (Y_i=1 s(i)=s)=α^(s)_m(i)+γ^(s)_k(i)+ _R^(s)R_i+ _A^(s)A_i+x_i θ^(s), All continuous predictors are standardized for comparability in the coefficient plots; plotted values are standardized log-odds ratios, i.e., log odds ratios for a 1-SD increase in the predictor. Stability analysis. To check whether the pooled coefficient is driven by one model or one underspecification level, we refit the same outcome model within each model-by-k cell in Logic-Q-MT and within each model-task-k cell in GeneReg-MT, omitting fixed effects inside the cell. Controls that are constant within a cell are dropped from that cell’s regression. A cell is marked NA if it has fewer than 50 usable interactions, no outcome variation, no variation in MSS relative mention rate, or a separated fit; NA cells are excluded from summary counts. Logic-Q-MT results. MSS relative mention rate is positively associated with final sufficiency (βz=0.528 _z=0.528, p=6.71×10−45p=6.71× 10^-45), whereas awareness of underspecification is near zero (βz=0.005 _z=0.005, p=0.853p=0.853) (Appendix Fig. 18). The same pattern holds in the turn-1-miss subset for second-turn hit: MSS relative mention rate remains positive (βz=0.365 _z=0.365, p=7.99×10−23p=7.99× 10^-23), while awareness again stays near zero (βz=0.010 _z=0.010, p=0.774p=0.774). The model-by-k stability diagnostic (Appendix Fig. 19) shows 23 positive cells out of 23 estimable cells for final sufficiency and 23 positive cells out of 24 estimable cells for second-turn hit; the corresponding nominally significant positive counts are 16 and 16. GeneReg-MT results. GeneReg-MT is directionally supportive but less clean. For final sufficiency, MSS relative mention rate is positive in both steady-state (βz=0.340 _z=0.340, p=5.39×10−17p=5.39× 10^-17) and marker tasks (βz=1.016 _z=1.016, p=3.77×10−27p=3.77× 10^-27) (Appendix Fig. 20). For second-turn hit after a first-turn miss, the same cue is again positive in steady-state (βz=0.274 _z=0.274, p=1.52×10−5p=1.52× 10^-5) and marker tasks (βz=0.590 _z=0.590, p=1.59×10−5p=1.59× 10^-5). However, the model-task-k stability diagnostic is much sparser: 85 estimable cells for final sufficiency and 20 estimable cells for second-turn hit, with many non-estimable recovery cells produced by the sample restriction above (Appendix Fig. 21). Adjustment sensitivity. We report the marginal effect (regression without problem factor) in addition to the fully adjusted model. The standardized log-odds ratio for MSS relative mention rate changes only modestly when problem factors are dropped: Logic-Q-MT final sufficiency 0.528 to 0.562, Logic-Q-MT second-turn hit 0.365 to 0.392, GeneReg-MT steady-state final sufficiency 0.340 to 0.334, GeneReg-MT marker final sufficiency 1.016 to 1.007, GeneReg-MT steady-state second-turn hit 0.274 to 0.342, and GeneReg-MT marker second-turn hit 0.590 to 0.620. We also verify that in the fixed-effect design, the VIF for MSS relative mention rate ranges from 1.158 to 1.563 across all Logic-Q-MT and GeneReg-MT analysis frames. Thus it is not collinear with the MSS-incidence control. Figure 18: Turn-1 CoT predictors in Logic-Q-MT. Each panel shows standardized log-odds ratios with 95% confidence intervals from a pooled model with model and k fixed effects and standard errors clustered by interaction. All predictors are standardized before fitting, so each value is the log odds ratio for a one-standard-deviation increase in the predictor. Left: final sufficiency over all interactions with at least one turn. Right: second-turn hit among interactions whose first-turn query misses the MSS and that continue to a second turn. MSS relative mention rate is the strongest CoT predictor in both panels (βz=0.528 _z=0.528 for final sufficiency; βz=0.365 _z=0.365 for second-turn hit), while awareness of underspecification remains near zero (βz=0.005 _z=0.005 for final sufficiency and βz=0.010 _z=0.010 for second-turn hit). Figure 19: Stability of MSS relative mention rate in Logic-Q-MT. Each cell refits the same outcome model within one model-by-k stratum, omitting fixed effects inside the stratum. Color indicates the standardized log-odds ratio for MSS relative mention rate; asterisks mark nominal p<0.05p<0.05. Controls that are constant within a cell are dropped from that cell’s regression; cells are marked NA when they have fewer than 50 usable interactions, no outcome variation, no variation in MSS relative mention rate, or a separated fit. Figure 20: Turn-1 CoT predictors in GeneReg-MT. The specification matches Logic-Q-MT conceptually but is fit separately for steady-state and marker tasks and uses a narrower gene-query template set to reduce false positives from regulatory-rule enumeration. MSS relative mention rate remains positive in both task families for final sufficiency (βz=0.340 _z=0.340 for steady state; βz=1.016 _z=1.016 for marker) and for second-turn hit after a first-turn miss (βz=0.274 _z=0.274 for steady state; βz=0.590 _z=0.590 for marker). Figure 21: Stability of MSS relative mention rate in GeneReg-MT. Each cell is a separate model-task-k regression with the same controls as the pooled model and heteroskedasticity-robust standard errors. Many recovery cells are NA because the outcome is defined only for interactions that both miss on turn 1 and continue to turn 2; the appendix text reports the exact NA criteria and summary counts. G.1.2 Example CoTs Annotated first-turn CoT examples. All excerpts below are real first-turn CoTs from original Logic-Q-MT forbid-alternatives runs. We report the raw target, turn-1 query, turn-2 query, and the MSS so each excerpt can be traced back to the source result JSON. Qwen3-4B-Thinking, target = thoughtless, turn-1 query = exuberant, turn-2 query = straightforward, MSS = straightforward, weary. “I need to ask about an attribute that is part of the antecedent for thoughtless. Let’s consider querying ‘weary’ because it’s in the second thoughtless rule. If I ask ‘Is Alice weary?’ and she is, then I need to know if she is distinct and straightforward.” Qwen3-30B-A3B-Thinking-FP8, target = smart, turn-1 query = proud, turn-2 query = plain, canonical MSS = long, plain, thoughtless. “…The most direct rule is ‘plain and proud -> smart.’ So we need both plain and proud. We can’t ask both, so we need to ask one that helps us get closer. If we ask about proud […] Similarly, if we ask about ‘plain’, and she’s plain, then we need to check if she’s proud…” Qwen3.5-122B-A10B-FP8, target = gifted, turn-1 query = talented, turn-2 query = mean, MSS = careless, mean. “…Path 1: ‘blushing’ AND ‘mean’ […] Forbidden to ask: blushing, courageous, cruel, cute, easy, fancy, gifted, helpful, plain, rational, shiny. Allowed to ask: calm, careless, frail, talented, […] mean. […] If I ask ‘careless’: No -> ‘gifted’ False. Yes -> need ‘talented’ AND ‘uptight’…” gpt-oss-20B-high, target = elegant, turn-1 query = versatile, turn-2 query = busy, MSS = busy, sincere, uptight. “…The rule that concludes elegant is rule 9: busy & elated & uptight => elegant. So to prove elegant, we need to prove that all three of those hold. So we could ask about ‘busy’, ‘elated’, or ‘uptight’. But we cannot ask about elated (forbidden)…” gpt-oss-120B-high, target = tame, turn-1 query = rational, turn-2 query = light, MSS = light, straightforward, talkative. “…Rule 18: calm & light & talkative => adorable. […] Thus we might want to ask about talkative and light. Light is allowed (not prohibited). Talkative is allowed. If we ask ‘Is Alice talkative?’ […] Alternatively, we could ask about light directly…” G.1.3 Additional results Fig. 22 shows the proportion of interactions that reach the 10-turn cap; complementarily, Appendix G.1.5 tests an intervention that rejects answer attempts issued before k queries, probing whether premature stopping is correctable under explicit feedback. Figure 22: Proportions of interactions that end at 10 turns for models in Logic-Q-MT task-solving, with no budget in prompt but capped at 10 turns. Figure 23: Performance of representative models with interactions ending on turn 10 in Logic-Q-MT task-solving, with no budget in prompt but capped at 10 or 20 turns. Figure 24: Recall with regard to the MSS in predicting missing variables. Same models and settings as Fig. 4; Jaccard similarity and recall are reported as a complement to accuracy. (a) k not provided; (b) k provided. Recall is lower when k is provided for k=2,3k=2,3 because forcing exactly k selections decreases the chance of overlap with a k-MSS, compared with being allowed to predict a larger set of variables. Table 20: Per-model accuracy of predicting the degree of underspecification k in Logic-Q-MT (multiple-choice k-prediction; cf. Fig. 3a). Each cell reports exact-match accuracy over 200 problems per k; predictions of “not ambiguous,” “not sure,” and unparseable responses are counted as incorrect. Model k=1k=1 k=2k=2 k=3k=3 Qwen3-30B-A3B-Thinking-FP8 0.720 0.505 0.405 Qwen3-30B-A3B-Thinking 0.710 0.495 0.330 Qwen3-4B-Thinking 0.770 0.340 0.125 Qwen3-Next-80B-A3B-Thinking-FP8 0.550 0.390 0.290 Qwen3.5-122B-A10B-FP8 0.835 0.465 0.265 Qwen3.5-27B 0.785 0.330 0.200 Qwen3.5-27B-FP8 0.825 0.395 0.200 Qwen3.5-35B-A3B 0.900 0.365 0.190 Qwen3.5-35B-A3B-FP8 0.900 0.390 0.235 Qwen3.5-4B 0.735 0.280 0.240 Qwen3.5-9B 0.845 0.355 0.155 GPT-5 0.935 0.500 0.255 GPT-5-mini 0.875 0.445 0.185 gpt-oss-120B-high 0.875 0.440 0.185 gpt-oss-120B-medium 0.765 0.520 0.250 gpt-oss-20B-high 0.915 0.435 0.275 gpt-oss-20B-medium 0.780 0.430 0.335 Table 21: Performance of LLMs on Logic-Q-MT missing variable and full-information problem-solving. We report missing-variable prediction performance when k is not provided or provided, and full-information problem-solving correctness as a reference upper bound for sequential task-solving. Model k k not provided k provided Full Info. Acc. Jac. Rec. Acc. Jac. Rec. Acc. Qwen3-30B-A3B-Thinking-FP8 1 0.250 0.314 0.390 0.320 0.320 0.320 0.885 2 0.070 0.238 0.302 0.165 0.323 0.402 0.948 3 0.040 0.250 0.283 0.135 0.410 0.522 0.976 Qwen3-4B-Thinking 1 0.230 0.288 0.350 0.320 0.320 0.320 0.855 2 0.065 0.222 0.252 0.120 0.280 0.360 0.959 3 0.030 0.236 0.247 0.095 0.408 0.533 0.852 Qwen3-Next-80B-A3B-Thinking-FP8 1 0.295 0.372 0.470 0.345 0.345 0.345 0.780 2 0.115 0.322 0.400 0.165 0.313 0.388 0.844 3 0.055 0.291 0.318 0.115 0.371 0.478 0.808 Qwen3.5-122B-A10B-FP8 1 0.235 0.374 0.630 0.435 0.435 0.435 – 2 0.065 0.272 0.438 0.210 0.340 0.405 – 3 0.075 0.324 0.443 0.175 0.436 0.542 – Qwen3.5-27B-FP8 1 0.300 0.403 0.590 0.470 0.470 0.470 1.000 2 0.060 0.295 0.445 0.205 0.343 0.412 1.000 3 0.050 0.293 0.392 0.130 0.370 0.472 1.000 Qwen3.5-35B-A3B-FP8 1 0.235 0.285 0.380 0.350 0.350 0.350 0.990 2 0.030 0.195 0.308 0.145 0.252 0.305 1.000 3 0.065 0.257 0.337 0.100 0.264 0.332 1.000 Qwen3.5-9B 1 0.245 0.340 0.515 0.425 0.425 0.425 0.995 2 0.095 0.262 0.398 0.220 0.345 0.408 1.000 3 0.035 0.294 0.415 0.165 0.386 0.480 0.980 Gemini-3-Flash 1 0.695 0.728 0.795 0.780 0.780 0.780 – 2 0.220 0.354 0.438 0.345 0.452 0.505 – 3 0.135 0.272 0.332 0.285 0.476 0.560 – Gemini-3.1-Pro 1 0.475 0.561 0.685 – – – – 2 0.285 0.409 0.498 – – – – 3 0.145 0.290 0.345 – – – – GPT-5 1 0.310 0.441 0.645 0.585 0.585 0.585 – 2 0.185 0.372 0.515 0.220 0.350 0.415 – 3 0.175 0.344 0.417 0.165 0.387 0.488 – GPT-5-mini 1 0.270 0.403 0.610 0.460 0.460 0.460 – 2 0.110 0.276 0.398 0.145 0.277 0.342 – 3 0.095 0.307 0.398 0.075 0.308 0.415 – gpt-oss-120B-high 1 0.230 0.368 0.600 0.325 0.325 0.325 1.000 2 0.090 0.305 0.465 0.115 0.257 0.328 0.990 3 0.130 0.348 0.433 0.130 0.382 0.493 1.000 gpt-oss-120B-medium 1 0.170 0.271 0.425 0.175 0.175 0.175 0.975 2 0.045 0.228 0.352 0.055 0.200 0.272 0.957 3 0.040 0.234 0.295 0.020 0.207 0.298 0.955 gpt-oss-20B-high 1 0.175 0.286 0.465 0.385 0.385 0.385 0.985 2 0.075 0.276 0.428 0.130 0.263 0.330 0.981 3 0.070 0.287 0.382 0.080 0.322 0.428 0.977 gpt-oss-20B-medium 1 0.160 0.270 0.430 0.235 0.235 0.235 0.800 2 0.085 0.268 0.395 0.065 0.202 0.270 0.830 3 0.040 0.261 0.345 0.055 0.304 0.417 0.898 Figure 25: Performance of LLMs in Logic-Q-MT task-solving with varying budget in prompt across models. Budgets are set in the form of “number of turns allowed” x “number of queries per turn allowed”. “No budget” refers to the setting where no budget is mentioned in the prompt. To avoid infinite loops, we cap the number of turns in the “No budget” setup at 10. This cap does not significantly affect final sufficiency (Fig. 23). With adversarial oracles. Figure 26: Performance of LLMs in GeneReg-MT marker and steady state identification task-solving with varying budget in prompt across models. Same setup as in Fig. 25. Figure 27: Proportion of tasks that have reached sufficiency at turn t per model, across each k, for Logic-Q-MT. Figure 28: Scatterplot underlying every cell of Fig. 5, plus a control row, in Logic-Q-MT. Each panel plots one of four behavioral features against final sufficiency; one dot per model, columns vary the true degree of underspecification k, the dashed grey line is the OLS fit, and the upper-left annotation reports the Pearson r. The first three rows correspond directly to the cells of the heatmap. The bottom row, avg number of turns - avg turn to sufficiency, is a control: it counts the turns each model uses past its first-sufficient turn, isolating the “keeps asking after it could stop” component from the raw turn count. Its correlation with final sufficiency strengthens with k (r=0.32→0.67r=0.32→ 0.67), mirroring the avg-number-of-turns row above and showing that on harder problems the benefit of longer interactions persists even after netting out when sufficiency is first reached. Figure 29: Heatmap of correlations between per-model behavioral features with average final sufficiency in GeneReg-MT dynamic steady state identification. Each cell is the Pearson r between the behavioral feature and average final sufficiency, computed across models within a fixed k. Figure 30: Heatmap of correlations between per-model behavioral features with average final sufficiency in GeneReg-MT dynamic marker identification. Each cell is the Pearson r between the behavioral feature and average final sufficiency, computed across models within a fixed k. Figure 31: Scatterplot underlying every cell of Fig. 29, plus a control row, in GeneReg-MT dynamic steady state identification. Each panel plots one of four behavioral features against final sufficiency; one dot per model, columns vary the true degree of underspecification k, the dashed grey line is the OLS fit, and the upper-left annotation reports the Pearson r. The first three rows correspond directly to the cells of the heatmap. The bottom row, avg number of turns - avg turn to sufficiency, is a control: it counts the turns each model uses past its first-sufficient turn, isolating the “keeps asking after it could stop” component from the raw turn count. Figure 32: Scatterplot underlying every cell of Fig. 30, plus a control row, in GeneReg-MT dynamic marker identification. Each panel plots one of four behavioral features against final sufficiency; one dot per model, columns vary the true degree of underspecification k, the dashed grey line is the OLS fit, and the upper-left annotation reports the Pearson r. The first three rows correspond directly to the cells of the heatmap. The bottom row, avg number of turns - avg turn to sufficiency, is a control: it counts the turns each model uses past its first-sufficient turn, isolating the “keeps asking after it could stop” component from the raw turn count. Figure 33: Recovery from a wrong first-turn query in k=2,3k=2,3 Logic-Q-MT tasks. Bars show final sufficiency for each model, partitioned by whether the model queries a correct variable in the first and second turns. For every model, the first-turn miss + second-turn hit (recovery) group performs within 10 percentage points of the first-turn hit group. A ⋆ marks models for which this near-parity is statistically supported by a one-sided Miettinen–Nurminen non-inferiority test with a 10p margin (p<0.05p<0.05). Figure 34: Recovery from a wrong first-turn query in k=2,3,4k=2,3,4 GeneReg-MT dynamic steady state identification. Bars show final sufficiency for each model, partitioned by whether the model queries a correct variable in the first and second turns. ▲ indicates that the first-turn miss + second-turn hit (recovery) group performs within 10 percentage points of the first-turn hit group. The number on each bar represents the number of interactions in each group. Groups with fewer than 10 interactions are not shown (a dash). No non-inferiority tests are performed due to the lack of power. Because some interactions emit zero or only one query, the miss+hit and miss+miss counts need not sum to first-turn miss; for the same reason, the totals of first-turn hit and first-turn miss vary slightly across models. Figure 35: Recovery from a wrong first-turn query in k=2,3,4k=2,3,4 GeneReg-MT dynamic marker identification. Bars show task-completion rate for each model, partitioned by whether the model queries a correct variable in the first and second turns. ▲ indicates that the first-turn miss + second-turn hit (recovery) group performs within 10 percentage points of the first-turn hit group. The number on each bar represents the number of interactions in each group. Groups with with fewer than 10 interactions are not shown (a dash). No non-inferiority tests are performed due to the lack of power. Because some interactions emit zero or only one query, the miss+hit and miss+miss counts need not sum to first-turn miss; for the same reason, the totals of first-turn hit and first-turn miss vary slightly across models. Figure 36: Sensitivity of the recovery criterion in Logic-Q-MT. For each threshold, we compute how many models satisfy the corresponding recovery criterion when comparing the “first-turn miss + second-turn hit” group against the “first-turn hit” group. The left panel uses a relative threshold based on the ratio of mean final sufficiency, while the right panel uses an absolute threshold based on the difference in mean final sufficiency. Results are shown for k=2k=2 and k=3k=3. (a) Steady-state identification. (b) Marker identification. Figure 37: Sensitivity of the recovery criterion in GeneReg-MT. For each threshold, we count how many models satisfy the recovery criterion when comparing the “first-turn miss + second-turn hit” group against the “first-turn hit” group. In each subfigure, the left panel uses a relative threshold based on the ratio of mean final sufficiency, while the right panel uses an absolute threshold based on the difference in mean final sufficiency. Results are shown for k=2,3,4k=2,3,4. G.1.4 Prompt sensitivity Because LLM performance can shift substantially under semantically minor prompt reformulations [26, 19], we quantify how sensitive the Logic-Q-MT and GeneReg-MT results are to the wording of the interaction prompt. We compare the default prompts (Appendix E.1 and Appendix E.1) against three variants: (P1) reordering the presentation of the rules, facts, and forbidden attributes; (P2) toggling the query-selection guidance, where the Logic-Q-MT default already contains this guidance, so P2 removes it, whereas the GeneReg-MT default does not, so P2 adds it; and (P3) dropping the reminder that the provided information may be insufficient. We evaluate Qwen3-4B-Thinking, Qwen3-30B-A3B-Thinking-FP8, gpt-oss-20B-high, and GPT-5-mini; the Logic-Q-MT runs use the same 1,200 tasks (600 problems, each with two target-value variants) as the main experiments. Noise calibration. A prompt variant should count as consequential only if it moves performance by more than run-to-run variability. We therefore rerun the original prompt under a different random seed (repl) to calibrate this noise and, for each model and variant, test whether the variant shifts final sufficiency more than the rerun does, i.e., H1:|Δ(orig,variant)|>|Δ(orig,repl)|H_1 (orig,variant) > (orig,repl) , where Δ is the signed difference in final sufficiency (variant minus original). p-values are obtained from a problem-level cluster bootstrap with 10,000 resamples and Holm-corrected over the model family. Table 22 reports the signed shifts. Table 22: Prompt sensitivity of final sufficiency in Logic-Q-MT and GeneReg-MT. Each cell reports the signed change in final sufficiency under a prompt variant, Δ=variant−original =variant-original, with the corresponding p-value in parentheses: a problem-level cluster bootstrap (10,000 resamples, Holm-corrected over the model family) tests whether the variant moves final sufficiency more than a rerun of the original prompt under a different seed. n.s. denotes p>0.05p>0.05. The Logic-Q-MT default prompt already contains the query-selection guidance, so P2 removes it, whereas the GeneReg-MT default does not, so P2 adds it. Variant Qwen3-4B-Thinking Qwen3-30B-A3B-Thinking-FP8 gpt-oss-20B-high GPT-5-mini Logic-Q-MT P1: reorder items +0.019+0.019 (n.s.) +0.053+0.053 (n.s.) +0.010+0.010 (n.s.) −0.005-0.005 (n.s.) P2: drop query-selection guidance +0.076+0.076 (.002) −0.109-0.109 (.006) −0.070-0.070 (.011) −0.040-0.040 (.011) P3: drop insufficiency reminder −0.141-0.141 (<<.001) −0.014-0.014 (n.s.) −0.027-0.027 (n.s.) −0.005-0.005 (n.s.) GeneReg-MT P1: reorder items −0.018-0.018 (n.s.) −0.040-0.040 (n.s.) −0.039-0.039 (n.s.) −0.012-0.012 (n.s.) P2: add query-selection guidance −0.037-0.037 (.046) −0.046-0.046 (.046) −0.031-0.031 (n.s.) +0.002+0.002 (n.s.) P3: drop insufficiency reminder −0.080-0.080 (<<.001) −0.137-0.137 (<<.001) −0.050-0.050 (.012) −0.023-0.023 (n.s.) Results. The findings are consistent across both domains. P1, a meaning-preserving reordering, has no measurable effect on any model in either domain: every cell stays within run-to-run noise, so the reported numbers are not artifacts of item order or formatting. P2 is content-bearing, so some change is expected; the effect is nevertheless small and model-dependent, the strongest model (GPT-5-mini) is essentially unaffected in both domains (−0.040-0.040 in Logic-Q-MT, +0.002+0.002 in GeneReg-MT), and the direction varies (removing the guidance helps Qwen3-4B-Thinking in Logic-Q-MT, while adding it slightly hurts the two Qwen models in GeneReg-MT), indicating that the default guidance is not what drives the reported failures. P3, removing the insufficiency reminder, lowers final sufficiency, with the effect concentrated in the smaller open-weight models (Qwen3-4B-Thinking, Qwen3-30B-A3B-Thinking-FP8, gpt-oss-20B-high) and no measurable effect on GPT-5-mini in either domain, suggesting that weaker models rely more on the explicit cue that the provided information may be insufficient and are less spontaneously calibrated. Overall, GPT-5-mini is robust to all three perturbations up to noise, apart from the small −0.040-0.040 P2 effect in Logic-Q-MT, and the sensitivity that does exist is confined to content-bearing edits and to weaker models, so the qualitative conclusions are not prompt artifacts. Prompt provenance and defaults. The prompts we use may not be globally optimal. The k-prediction and MSS-identification prompts were minimally adapted from QuestBench [15] to support multiple jointly necessary variables, and the multi-turn evaluation prompts were fixed before the full model comparison and shared across all models, with no model-specific or test-instance tuning. We adopt the no-budget formulation as the default because explicitly stating a turn budget can change the stopping behavior being evaluated; the turn-budget ablation and the perturbations above both show that prompting shapes information-seeking behavior, and the development of better prompting strategies for multi-turn information seeking is left to future work. G.1.5 Preventing premature answers Intervention. Directly forcing interaction to continue until the acquired information is sufficient would make the outcome true by construction. We therefore test a weaker intervention: in a k-underspecified task, any attempt to answer before issuing k queries is rejected, and the model is asked to query again. Query selection remains unconstrained, and the model may stop freely once it has issued k queries, whether or not those queries are actually sufficient. The intervention thus prevents clear under-querying without guaranteeing sufficiency. We focus on k=3k=3, since tasks with a higher degree of underspecification show a higher rate of premature stopping. Results. Table 23 compares final sufficiency and the average number of turns between the original and force-ask protocols on Logic-Q-MT at k=3k=3. Preventing early stopping significantly improves final sufficiency for both Qwen models (+9.7+9.7 p, p=0.003p=0.003 for Qwen3-4B-Thinking; +25.7+25.7 p, p<5×10−4p<5× 10^-4 for Qwen3-30B-A3B-Thinking-FP8; exact McNemar tests), whereas the effect for gpt-oss-20B-high and GPT-5-mini is insignificant. Interestingly, the intervention also increases turn counts beyond what is needed merely to satisfy the k-query minimum. A possible explanation is that rejecting an early answer signals to the model that its information is currently insufficient—a signal it would not otherwise receive—so that it becomes more cautious afterward. Interpretation. This setting arguably leaks the degree of underspecification and enforces continued querying in a way that is not typical of how LLMs seek information. We therefore view the gains as evidence of a latent capability that can be elicited under explicit correction, rather than as evidence of the models’ spontaneous calibration. Table 23: Effect of preventing premature answers on Logic-Q-MT at k=3k=3 (400 episodes per model). Any attempt to answer before issuing k queries is rejected and the model is asked to query again; query selection remains unconstrained, and the model may stop freely once k queries have been issued. Final sufficiency is compared with exact McNemar tests and the average number of turns with Wilcoxon signed-rank tests, both paired at the episode level. Model Final sufficiency Number of turns Original Force-ask Change (p) p (McNemar) Original Force-ask Change p (Wilcoxon) Qwen3-4B-Thinking 0.560 0.657 +9.7+9.7 0.003 4.725 5.192 +0.467+0.467 <5×10−4<5× 10^-4 Qwen3-30B-A3B-Thinking-FP8 0.275 0.532 +25.7+25.7 <5×10−4<5× 10^-4 3.743 4.910 +1.167+1.167 <5×10−4<5× 10^-4 gpt-oss-20B-high 0.818 0.825 +0.7+0.7 0.824 6.470 6.678 +0.208+0.208 0.187 GPT-5-mini 0.858 0.887 +2.9+2.9 0.175 5.530 5.647 +0.117+0.117 0.471 G.1.6 Sensitivity to the designated MSS MSS multiplicity across domains. GeneReg-MT, GSME-Q-MT, and ClinGuide-MT have a unique MSS by construction; for GeneReg-MT we additionally verified uniqueness exhaustively. Multiple MSSs are common in Logic-Q-MT: 96.8% of problems have more than one, with an average of 5.98, 8.74, and 10.34 MSSs for k=1k=1, 22, and 33, respectively (8.35 overall). Our primary sequential metric, final sufficiency, is invariant to the choice of MSS: it checks whether the acquired information uniquely determines the target, irrespective of the MSS. The set of queryable variables, however, does depend on the designated MSS, which can affect model behavior. Because evaluation outcomes can be sensitive to seemingly incidental design choices [26, 19], we quantify the sensitivity of Logic-Q-MT results to the designated MSS directly. Resampling design. We independently resampled two alternative canonical MSSs (altgt1 and altgt2) for every Logic-Q-MT problem; all three canonical MSSs are pairwise different for 538 of the 600 problems (89.7%; Table 24). We then re-evaluated four representative models on the two Logic-Q-MT variants with alternative canonical MSSs, and additionally re-ran the original tasks with an identical configuration but a different random seed (repl), which calibrates run-to-run noise. For every model and redraw, we test whether the redraw effect exceeds this noise, H1:|Δ(orig,alt)|>|Δ(orig,repl)|H_1\!:\,| (orig,alt)|>| (orig,repl)|, via a problem-level cluster bootstrap (10,000 resamples). All 8 tests per metric are run and reported, with the raw one-sided p-value and its Holm adjustment over the 8. We focus on k=3k=3, the stratum with the largest MSS multiplicity. Table 24: Overlap classes of the three canonical MSS draws per Logic-Q-MT problem: the original designated MSS and two independently resampled alternatives (altgt1, altgt2). Class Problems All three identical 19 Two alternatives identical, both different from the original 43 All three pairwise different 538 (89.7%) Table 25: Sensitivity of final sufficiency to the designated MSS in Logic-Q-MT at k=3k=3. Δ columns are signed (run minus original): Δsuff(alt−orig) _suff(alt-orig) compares the alternative-MSS variant with the original run, and Δsuff(repl−orig) _suff(repl-orig) compares a rerun of the original configuration with a different random seed. The test statistic is |Δalt|−|Δrepl|| _alt|-| _repl|, i.e., whether the redraw effect exceeds run-to-run noise, assessed by a problem-level cluster bootstrap (10,000 resamples) with the 95% percentile confidence interval shown; pbootp_boot is the raw one-sided bootstrap p-value and pHolmp_Holm its Holm adjustment over the 8 tests within each metric. n.s. denotes p>0.2p>0.2. Statistics are computed from unrounded values and rounded independently, so displayed columns may disagree in the last digit. Model Comparison Δsuff(alt−orig) _suff(alt-orig) Δsuff(repl−orig) _suff(repl-orig) |Δalt|−|Δrepl|| _alt|-| _repl| 95% CI pbootp_boot pHolmp_Holm Qwen3-4B-Thinking vs altgt1 +0.037+0.037 −0.015-0.015 +0.022+0.022 [−0.057,+0.088][-0.057,+0.088] n.s. n.s. Qwen3-4B-Thinking vs altgt2 +0.035+0.035 −0.015-0.015 +0.020+0.020 [−0.057,+0.088][-0.057,+0.088] n.s. n.s. Qwen3-30B-A3B-Thinking-FP8 vs altgt1 +0.072+0.072 +0.027+0.027 +0.045+0.045 [−0.018,+0.100][-0.018,+0.100] 0.090 n.s. Qwen3-30B-A3B-Thinking-FP8 vs altgt2 −0.005-0.005 +0.027+0.027 −0.022-0.022 [−0.062,+0.050][-0.062,+0.050] n.s. n.s. gpt-oss-20B-high vs altgt1 +0.065+0.065 +0.017+0.017 +0.047+0.047 [−0.005,+0.088][-0.005,+0.088] 0.042 n.s. gpt-oss-20B-high vs altgt2 +0.052+0.052 +0.017+0.017 +0.035+0.035 [−0.015,+0.077][-0.015,+0.077] 0.117 n.s. GPT-5-mini vs altgt1 +0.027+0.027 −0.005-0.005 +0.022+0.022 [−0.040,+0.057][-0.040,+0.057] n.s. n.s. GPT-5-mini vs altgt2 +0.007+0.007 −0.005-0.005 +0.002+0.002 [−0.040,+0.037][-0.040,+0.037] n.s. n.s. Table 26: Sensitivity of the number of turns to the designated MSS in Logic-Q-MT at k=3k=3. Same protocol as Table 25: Δ columns are signed (run minus original), the test statistic |Δalt|−|Δrepl|| _alt|-| _repl| is assessed by a problem-level cluster bootstrap (10,000 resamples), and Holm adjustment is over the 8 tests within each metric. n.s. denotes p>0.2p>0.2. Model Comparison Δturns(alt−orig) _turns(alt-orig) Δturns(repl−orig) _turns(repl-orig) |Δalt|−|Δrepl|| _alt|-| _repl| 95% CI pbootp_boot pHolmp_Holm Qwen3-4B-Thinking vs altgt1 −0.355-0.355 −0.087-0.087 +0.268+0.268 [−0.013,+0.485][-0.013,+0.485] 0.032 n.s. Qwen3-4B-Thinking vs altgt2 −0.557-0.557 −0.087-0.087 +0.470+0.470 [+0.192,+0.683][+0.192,+0.683] 0.001 0.006 Qwen3-30B-A3B-Thinking-FP8 vs altgt1 −0.040-0.040 −0.058-0.058 −0.018-0.018 [−0.188,+0.167][-0.188,+0.167] n.s. n.s. Qwen3-30B-A3B-Thinking-FP8 vs altgt2 −0.048-0.048 −0.058-0.058 −0.010-0.010 [−0.198,+0.183][-0.198,+0.183] n.s. n.s. gpt-oss-20B-high vs altgt1 −0.345-0.345 −0.007-0.007 +0.338+0.338 [−0.125,+0.542][-0.125,+0.542] 0.090 n.s. gpt-oss-20B-high vs altgt2 −0.270-0.270 −0.007-0.007 +0.263+0.263 [−0.177,+0.475][-0.177,+0.475] 0.173 n.s. GPT-5-mini vs altgt1 −0.303-0.303 +0.165+0.165 +0.138+0.138 [−0.337,+0.525][-0.337,+0.525] n.s. n.s. GPT-5-mini vs altgt2 −0.293-0.293 +0.165+0.165 +0.128+0.128 [−0.330,+0.487][-0.330,+0.487] n.s. n.s. Results. Tables 25 and 26 report the comparisons. Alternative-MSS variants yield modest gains: final sufficiency increases by up to 7.2 percentage points at k=3k=3 (positive in 7 of 8 comparisons) while requiring slightly fewer turns. Most differences fall within run-to-run noise: across all 16 noise-anchored comparisons, only Qwen3-4B-Thinking’s turn reduction on altgt2 survives Holm correction, and two further comparisons reach uncorrected p<0.05p<0.05 (Qwen3-4B-Thinking’s turn reduction on altgt1, and gpt-oss-20B-high’s final-sufficiency shift on altgt1). Why alternative draws are slightly easier. The direction of the shift reflects a construction asymmetry: canonical MSSs had to be certified by forward chaining during dataset construction, whereas alternative MSSs could also be sufficient by refutation, making them shallower and easier to identify. Table 27 quantifies this. At k=3k=3, all original canonical MSSs are forward-derivable with mean depth 4.40, versus roughly 60% and mean depth 3.5 for the resampled draws. The original draw is therefore a restricted and systematically deeper subpopulation, and a shallower MSS is easier to identify; in this sense the designated MSS is the harder one. Table 27: Forward-derivability and derivation depth of the designated MSS by draw at k=3k=3. % forward-derivable is the fraction of designated MSSs whose sufficiency admits an explicit forward-chaining (unit-propagation) derivation; MSS depth is the length of that derivation. Mean and median depths are computed over forward-derivable draws only, as depth is undefined for MSSs whose sufficiency holds only by refutation; for the original draw this includes all problems. Draw % forward-derivable Mean MSS depth Median MSS depth original 100.0% 4.400 4.0 altgt1 59.0% 3.550 4.0 altgt2 60.5% 3.499 3.0 G.2 GSME-Q-MT Strong single-turn performance does not guarantee reliable information seeking. As shown in Figure 39, several models perform well when the missing information is requested in a single turn, but become less reliable when the same information must be acquired through interaction. This gap is small on the GSME-Q-MT, where most instances are relatively simple and many models remain near saturation. In contrast, the GSME-Q-MT-Ext exposes clearer differences across models and values of k. For example, Qwen3-4B-Thinking and Qwen3-30B-A3B-Thinking-FP8 show increasingly large drops as k grows, suggesting that the difficulty is not solving the arithmetic problem, but managing the information-seeking process needed to make the problem fully specified. Interestingly, GPT-5-mini remains stable across both settings, while Gemini-3-Flash shows only minor changes, indicating that some models are better able to preserve their single-turn planning ability during interaction. Figure 38: Answer accuracy on GSME across different values of k. The original GSME setting is nearly saturated across models, whereas the DAG-generated complex GSME setting reveals a sharp degradation in the multi-turn setting. Figure 39: Analysis of multi-turn degradation in GSME. Accuracy change from single-turn to multi-turn querying, measured as multi-turn accuracy minus single-turn accuracy. Negative values indicate degradation under multi-turn interaction. G.3 ClinGuide-MT full results Appendix Fig. 40 reports final accuracy stratified by query coverage and query order across k∈3,4k∈\3,4\ and different numbers of distractors 0,10,200,10,20. Across nearly all models and settings, interactions that cover MSS in full achieve substantially higher accuracy than those that only partially cover it, confirming that acquiring the necessary information is a prerequisite for accurate final prediction. Within both the full-coverage and partial-coverage groups, following the order induced by the clinical diagnostic pathways generally improves accuracy, showing that the order of information acquisition does affect downstream reasoning. This effect is especially pronounced in more difficult settings with larger k and more distractors, where incorrect ordering often leads to noticeable accuracy drops even among MSS all covered interactions. Appendix Fig. 41 further investigates the impact of query coverage, order correctness, and query correctness on final accuracy using regression analysis on their associations with final accuracy Yi=α+γki+βcovQueryCov(Q^i)+βordOrdCorr(Q^i)+βcorrQueryCorr(Q^i)+εiY_i=α+ _k_i+ _covQueryCov( Q_i)+ _ordOrdCorr( Q_i)+ _corrQueryCorr( Q_i)+ _i. This can be calculated with the metrics we defined in Appendix C.3. Across model and setting pairs, query coverage remains the strongest and most stable positive predictor to final accuracy, as it is most frequently the top-ranked predictor. Order correctness also contributes positively in most settings, remaining the second-ranked predictor to final accuracy. Query correctness, which captures avoiding off-branch or irrelevant queries, provides an additional positive association and becomes more salient in more difficult settings. Together, these full results support the main-text conclusion that to achieve high final accuracy in ClinGuide-MT problem, the model needs to ask the correct question and in the correct order. Figure 40: ClinGuide-MT final accuracy by MSS coverage and MSS ordering in the queried variables (a-f: k=3,4k=3,4, and 0,10,200,10,20 distractors). Figure 41: The effect of query coverage, order correctness, and query correctness on final accuracy for ClinGuide-MT Problem (a-f: k=3,4k=3,4, and 0,10,200,10,20 distractors). G.3.1 Open-book evaluation The default ClinGuide-MT evaluation is closed-book: no diagnostic reference material is provided, so recognizing which information is missing partly depends on the model’s internal medical knowledge. To explicitly separate this from information-seeking, we additionally evaluate an open-book setting in which models are given all 59 diagnostic algorithms extracted from the source textbook [7], in their original wording, including the algorithm relevant to each case (pathway provenance and validation are described in Appendix D.4.1). These diagnostic algorithms are in decision-tree format with an explicit chart of procedure; the patient-specific values along the pathway are to be acquired through questioning. Effect on final accuracy. Providing the full set of diagnostic algorithms substantially improves final accuracy across all four evaluated models and both difficulty levels (Table 28), with the largest gains for Qwen3-4B-Thinking. Performance is nevertheless far from saturated even in this setting, indicating that access to the relevant diagnostic algorithm alone does not solve the task. Table 28: ClinGuide-MT final accuracy in the closed-book and open-book settings for k=3k=3 and k=4k=4 tasks. In the open-book setting, the model is given all 59 diagnostic decision trees from the source textbook [7] in their original wording, including the tree relevant to the case. Model = k=3 = k=4 Closed-book Open-book Closed-book Open-book GPT-5-mini 55.7% 88.4% 54.6% 85.0% gpt-oss-20B-high 28.1% 56.5% 29.5% 54.2% Qwen3-30B-A3B-Thinking-FP8 38.1% 71.1% 33.9% 64.3% Qwen3-4B-Thinking 32.2% 78.4% 31.7% 80.2% Coverage and ordering effects persist. Table 29 stratifies final accuracy by MSS coverage and query order in both settings. The coverage and ordering findings established above carry over to the open-book setting wherever the strata are populated: interactions that cover the full MSS attain the highest accuracy, and querying in the order the diagnostic algorithm suggests further boosts performance. Table 29: ClinGuide-MT final accuracy stratified by MSS coverage and query order for k∈3,4k∈\3,4\ in the closed-book setting (no diagnostic decision trees provided) and the open-book setting (all 59 diagnostic decision trees provided). Column headers abbreviate the strata: All/Partial denotes full versus partial MSS coverage, and Correct/Incorrect denotes whether the queries follow the order induced by the diagnostic pathway. Each cell reports final accuracy with the stratum size N in parentheses; “–” marks strata with fewer than five samples, which are not reported because of insufficient statistical power. Model k Closed-book (decision trees =0=0) Open-book (all 59 decision trees) All/Correct All/Incorrect Partial/Correct Partial/Incorrect All/Correct All/Incorrect Partial/Correct Partial/Incorrect Qwen3-30B-A3B-Thinking-FP8 3 69.6% (N=23) 50.0% (N=40) 38.2% (N=251) 25.0% (N=28) 94.0% (N=184) – 50.0% (N=168) – Qwen3-30B-A3B-Thinking-FP8 4 83.3% (N=6) 59.1% (N=22) 29.6% (N=152) 37.8% (N=37) 97.8% (N=93) – 41.5% (N=123) 28.6% (N=7) Qwen3-4B-Thinking 3 63.6% (N=22) 40.0% (N=45) 29.2% (N=271) 22.2% (N=27) 94.4% (N=195) 88.9% (N=18) 60.8% (N=143) 40.0% (N=5) Qwen3-4B-Thinking 4 – 38.1% (N=21) 35.3% (N=150) 16.0% (N=50) 93.6% (N=110) 100.0% (N=7) 67.0% (N=103) 50.0% (N=6) GPT-5-mini 3 82.0% (N=61) 61.7% (N=60) 52.9% (N=210) 25.8% (N=31) 97.9% (N=243) 93.3% (N=15) 68.9% (N=103) 80.0% (N=5) GPT-5-mini 4 90.0% (N=10) 56.1% (N=41) 55.6% (N=124) 46.0% (N=50) 100.0% (N=111) 92.9% (N=14) 68.1% (N=94) 62.5% (N=8) gpt-oss-20B-high 3 39.1% (N=23) 26.0% (N=50) 33.8% (N=219) 15.2% (N=46) 74.8% (N=155) 63.0% (N=27) 43.8% (N=160) – gpt-oss-20B-high 4 – 29.2% (N=24) 33.1% (N=124) 24.6% (N=69) 85.4% (N=48) 46.2% (N=13) 46.2% (N=143) 57.1% (N=14) Note that this is a favorable, near-upper-bound version of open-book settings. Although all 59 decision trees are provided and the model must still locate the relevant one, the trees are given in the exact wording used to construct the tasks and with a clear procedural structure, so solving largely reduces to matching the case to the right tree and node and then following the branch, rather than deciding what is relevant within a large or noisy knowledge source. The large gains are therefore expected and likely overstate real-world open-book performance. Even in this favorable setting, however, accuracy is not saturated and the coverage and ordering effects persist, so the residual errors reflect failures to identify, order, and acquire case-specific information rather than missing medical knowledge. G.4 20Q evaluations G.4.1 Full results (a) Common. (b) Thing. Figure 42: Accuracy versus offline question informativeness on the 20Q tasks. Bars show final guessing accuracy, and lines show the average offline question-quality score of the questions asked by each guesser model. Better questions generally improve accuracy, but question informativeness alone does not determine success. Figure 42 compares final accuracy with our offline question-quality score across datasets and examiners. Overall, models that ask higher-quality questions tend to achieve higher final accuracy, suggesting that informative question selection is an important factor in 20Q performance. This trend is especially clear under the GPT-5-mini examiner, where stronger guesser models obtain both higher question-quality scores and higher final accuracy on both Common and Thing. However, this relationship is not deterministic. For example, under the Qwen3-30B-A3B-Instruct-FP8 examiner, some models achieve similar or even lower question-quality scores while maintaining competitive final accuracy. This indicates that final success depends not only on asking informative questions, but also on whether the model can integrate the accumulated interaction history and use the remaining evidence to make a correct final guess. Thus, question informativeness captures an important but incomplete aspect of multi-turn information seeking. (a) Examiner: GPT-5-mini. (b) Examiner: Qwen3-30B-A3B-Instruct-FP8. Figure 43: Remaining entropy of the candidate distribution across turns. Each curve tracks the average posterior uncertainty after each turn for a given guesser model, dataset, and examiner. Multi-turn interaction consistently reduces uncertainty, and later turns become less effective. Figure 43 shows the remaining entropy of the candidate distribution after each turn. Across both datasets, both examiners, and almost all guesser models, entropy decreases steadily over the interaction. This confirms that the generated questions are informative overall and that the interaction progressively narrows the candidate space. At the same time, most curves exhibit a clear slowdown in later turns. The largest entropy reduction usually occurs in the early stage, when models ask broad categorical questions that separate large groups of candidates. After the candidate space has been narrowed, later turns require more fine-grained follow-up questions, and many models show weaker marginal progress. This suggests that a central challenge in 20Q is not only initiating useful information seeking, but sustaining discriminative questioning after the broad category has already been identified. (a) Examiner: GPT-5-mini. (b) Examiner: Qwen3-30B-A3B-Instruct-FP8. Figure 44: Pass mass across turns in the 20Q tasks. Pass mass denotes the posterior support mass of candidates for which the current question would receive a pass response, meaning that the question is ambiguous or not cleanly answerable by yes or no for those candidates. G.4.2 Case study Case-study setup. To better understand why models can ask seemingly high-quality questions yet still achieve low final accuracy in the 20 Questions game, we conduct a qualitative case-study analysis of representative failure interaction. For each selected episode, we jointly visualize three elements: the QA trace, the remaining entropy of the candidate set after each turn, and the support mass assigned to the answer pass. Remaining entropy measures how much uncertainty is left in the search state, while pass-support mass captures how much of the current candidate space is consistent with an ambiguous or non-committal answer. We select four cases that reflect distinct failure patterns repeatedly observed in the logs. In this analysis, we focus on QA traces generated by Qwen3-4B-Thinking, because this model attains relatively high question-quality scores but performs noticeably worse in recovering the final target. Case-study observations. The four examples in Figure 45 illustrate several recurring failure patterns in 20 questions, including weak final disambiguation, ambiguity accumulation, inconsistent belief-state updates, and search at the wrong abstraction level. Despite these differences, they share a common structure: the model often makes some progress in narrowing the candidate space, but fails to reliably consolidate that progress into a correct final answer. This suggests that effective information seeking depends not only on asking high-quality questions in isolation, but also on maintaining a coherent search state, using ambiguous evidence appropriately, and refining the search at the right semantic granularity. (a) Weak final disambiguation. The model narrows the search to the correct semantic region but fails to separate the true target from nearby alternatives in the final stage. Late ambiguous questions and repeated pass answers leave the belief insufficiently resolved, leading to a wrong final guess. (b) Ambiguity accumulation. Repeated pass answers on material- and origin-related attributes destabilize the search process. Instead of clarifying the object’s core identity, the model continues refining along an ambiguous axis and eventually drifts toward an incorrect target. (c) Belief-state update failure. Although the interaction provides useful evidence that the target belongs to a bear-like category, the model fails to consistently update and maintain its belief state. It revisits incompatible candidates and ends with an incorrect prediction. (d) Wrong abstraction level. The target requires reasoning in a functional or object-level semantic space, but the model keeps searching through material and chemistry attributes. This misaligned abstraction level leads the interaction away from the target and produces a nonsensical final answer. Figure 45: Representative failure modes in 20 questions.