Evaluating multi-turn information seeking in LLMs.
†Harvard University · ‡Google DeepMind
Large language models often operate under incomplete information in multi-turn interactions, because a user task may be underspecified. 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. 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 evaluations 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. Model priors and the ability to generate answers therefore confound the evaluation.
In MediQ, a 30B model answers correctly in roughly 60–70% of cases from the initial incomplete information alone, so final accuracy overstates the ability to seek information.
Representing an underspecified task as a constraint satisfaction problem 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.
We formalize multi-turn information seeking as solving a k-underspecified constraint satisfaction problem, 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 study three components of multi-turn information seeking: which variables the model queries, in which order it queries them, and how it uses the acquired information.
A problem is a tuple of variables, their domains, logical constraints, an observed partial assignment, and a target variable. The feasible space holds every assignment still consistent with the constraints and the observation. The target is known when all feasible assignments agree on its value; when several values remain possible, the problem is underspecified. A set of queryable variables is sufficient if fixing their values always determines the target. A smallest such set is a minimal k-sufficient set (k-MSS), and its size k is the degree of underspecification.
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.
5,251 problems · 9,006 task instances · 5 domains
Rule-based logical reasoning environments where models sequentially identify and query the missing facts needed to prove or disprove a target proposition.
Grade-school math problems in equation form, with human-annotated missing conditions required to compute an answer, extended to multi-turn by masking multiple quantities at once. The Ext variant is generated from DAG-structured arithmetic programs with deeper dependency chains, larger variable sets, and rigorously validated k-MSSs.
Boolean gene regulatory networks where variables are gene-expression states and the target is a steady state or a specific marker-gene value, testing navigation of cyclic dependencies.
Diagnostic decision trees from clinical guidelines and textbooks, where the variables are symptoms, risk factors, and test results, and the target is a diagnosis or management decision. Root-to-leaf pathways encode conditional dependencies. The curated guideline algorithms are not redistributed; the curation pipeline is released.
The 20 Questions game as an open-domain setting. The model deduces a hidden target by generating natural-language yes/no questions, each of which partitions the candidate set instead of querying a predefined variable.
Multi-turn interaction exercises several abilities at once, so we evaluate three of them separately. The first two present the problem on its own, without any dialogue, so a failure reflects how the model assesses the problem rather than how it conducts an interaction. The third evaluates the interaction itself.
LLMs recognize when context is insufficient, but underestimate how much additional information is required. Models rarely mistake an underspecified problem for a complete one, but their estimates of the degree of underspecification degrade as more variables are hidden, and the errors skew toward underestimation.
Accuracy of predicting the true k and under- versus over-prediction rates in Logic-Q-MT.
Knowing that information is missing does not mean knowing what information is needed. Even when given the true k, models struggle to pinpoint which variables are needed: exact-set accuracy remains low whenever two or more variables are required.
MSS exact-set accuracy in Logic-Q-MT, with k not provided or provided.
Spreading questions across turns usually beats asking them all at once, even under the same total query budget. The same model reaches final sufficiency more often when it queries, reads the answer, and queries again than when it issues all its queries in one batch, and additional turns generally help.
Final sufficiency in Logic-Q-MT under different turn and per-turn query budgets.
In highly underspecified problems, success depends less on asking the perfect first question and more on sustaining effective information acquisition across turns. Early-turn query correctness predicts final sufficiency when k is small; at larger k, models are separated by whether they keep identifying useful variables across turns.
Correlation between behavioral features and final sufficiency in Logic-Q-MT.
An incorrect first question is often recoverable if the model continues searching for target-relevant information. Dialogues whose first query misses but whose second finds a needed variable reach final sufficiency nearly as often as dialogues that query correctly from the start.
Final sufficiency in Logic-Q-MT for first-turn hit versus first-turn miss followed by second-turn hit. A star marks models where the two are statistically non-inferior at a 10 percentage-point margin.
In order-dependent settings, asking the right questions is not enough if they are asked in the wrong order. Clinical diagnostic pathways impose conditional dependencies, since an earlier finding determines which variables are relevant next. Violating that order lowers final accuracy even when the model eventually acquires every necessary variable.
ClinGuide-MT final accuracy stratified by MSS coverage and MSS ordering.
Asking informative questions is necessary but not sufficient for identifying the target. Models with similar question informativeness can differ substantially in final accuracy: success depends on how a model integrates the acquired evidence, not only on acquiring it.
Accuracy versus normalized information gain across examiners, on the Thing pool.
Target identification accuracy across answer models given the same QA dialogue.
LLMs are better at coarse-grained narrowing than fine-grained disambiguation. Remaining entropy falls quickly in early turns as models identify the target’s broad category, but the curves often flatten once only a few similar candidates remain.
Remaining entropy across turns under the GPT-5-mini examiner.
A partially informative answer is not a failed turn. High pass-support mass does not consistently lower final accuracy. Stronger models extract evidence from responses that do not separate the candidates and use it in later turns to narrow the remaining target values.
Probability mass of candidates consistent with pass under the GPT-5-mini examiner.
Across all five domains, current LLMs detect underspecification but underestimate its degree, query incomplete sets of variables, and stop before the acquired information determines the target. Information seeking also dissociates from answer generation: models that answer correctly once they are given all the needed variables still differ widely in final sufficiency, and other models recover the target differently from identical dialogues. Final accuracy alone therefore does not measure interactive competence.
@misc{huang2026mtinfoseek,
title={Do LLMs Know What to Ask and When? Evaluating Multi-Turn Information Seeking},
author={Huang, Yepeng and Zhang, Jiawen and Dai, Michelle and Su, Xiaorui and Gao, Shanghua and Wang, Zi and Zitnik, Marinka},
year={2026},
eprint={2608.14808},
archivePrefix={arXiv},
primaryClass={cs.AI},
url={https://arxiv.org/abs/2608.14808}
}