BED-LLM: Intelligent Information Gathering with LLMs and Bayesian Experimental Design
Authors: Deepro Choudhury
Sinead Williamson
Adam Golinski
Ning Miao
Freddie Bickford Smith
Michael Kirchhof
Yizhe Zhang
Tom Rainforth
Venue: ICLR 2026 Poster (2026)
Keywords: experimental design
Bayesian experimental design
BED
expected information gain
EIG
information gain
Bayesian
uncertainty
LLM
conversational agent
clarification
question asking
Primary area: foundation or frontier models, including LLMs

Abstract: We propose a general-purpose approach for improving the ability of large language models (LLMs) to intelligently and adaptively gather information from a user or other external source using the framework of sequential Bayesian experimental design (BED). This enables LLMs to act as effective multi-turn conversational agents and interactively interface with external environments. Our approach, which we call BED-LLM (Bayesian experimental design with large language models), is based on iteratively choosing questions or queries that maximize the expected information gain (EIG) with respect to a variable of interest given the responses gathered previously. We show how this EIG can be formulated (and then estimated) in a principled way using a probabilistic model derived from the LLM's predictive distributions and provide detailed insights into key decisions in its construction and updating procedure. We find that BED-LLM achieves substantial gains in performance across a wide range of tests based on the 20 Questions game and using the LLM to actively infer user preferences, compared to purely prompting-based design generation and other adaptive design strategies.

Published as a conference paper at ICLR 2026
BED-LLM: INTELLIGENT INFORMATION GATHERING WITH LLMS AND BAYESIAN EXPERIMENTAL DESIGN
Deepro Choudhury"
Sinead Williamson'
Adam Goliński!
Ning Miao Tom Rainforth"
Freddie Bickford Smith
Michael Kirchhof
Yizhe Zhang
*University of Oxford
Apple
*City University Hong Kong
ABSTRACT
We propose general-purpor approach for improving the ability of large language models (LLMs) to intelligently and adaptively gather information from user other external source using the framework of sequential Bayesian experimental design (BED). This enables LLMs act as effective multi-turn conversational agents and interactively interface with external environments. Our approach, which we call BED-LLMM (Bayesian experimental design with large language models), is based on iteratively choosing questions queries that maximize the expected information gain (EIG) with respect to a variable interest given the responses gathered previously. We show how this EIG can be formulated (and then estimated) in a principled way using a probabilistic model derived from the LLM's predictive distributions and provide detailed insights into key decisions in its construction and updating procedure. We find that BED-LLM achieves substantial gains in performance across a wide range of tests based on the 20 Questions game and using the LLM to actively infer user preferences, compared to purely prompting-bast bbsed design generation and other adaptive design strategies.
INTRODUCTION
Intelligent information gathering- the ability to ask the right questions at the right time is funda- mental to effective Al systems. However, despite their many successes, LLMs currently fall short on proactively seeking out information from user or external environment in an adaptive manner (Laban al., 2025; Li al., 2025c). For example, they have been shown to perform poorly on multi-turn guessing games (Bertolazzi et al., 2023; Zhang et al., 2024), task clarification (Chi et al., 2024), IT task automation (Jha et al., 2025) and multi-step tool use (Patil et al., 2025). particular, while modern LLMs are often capable of producing coherent and insightful questions (or other external queries) in a single-turn setting, they typically struggle to appropriately tailor their questions to previously gathered responses interactive tasks (Bertolazzi et al., 2023; Patil al., 2025).
There is, therefore, a pressing need to improve the ability of LLMs to adaptively ask questions based on previous responses, and gather information in targeted manner. Such capabilities essential for a wide variety of problems, such as clarifying user intent, personalizing model behavior to a particular user, or generally acting as effective multi-turn conversational agents. They are also critical if we want to use LLMs in data gathering tasks or as automated agents in decision-making pipelines (Wu al., 2025). In turn, these capabilities are essential across domains ranging from medical diag- nosis (Hirosawa et al., 2024). troubleshooting (Jha et al., 2025), preference learning (Chakraborty al., 2024: Handa et al., 2024: Ouyang al., 2022) and tutoring systems (Kestin et al., 2025: Liu et al., 2024a), to conducting automated surveys (Aher et al., 2023; Jacobsen et al., 2025; Lee et al., 2024) and AI-driven scientific inquiries (Lu et al., 2024; Mandal al., 2025). Note that all these problems it is not enough for the LLM to generate full sets of suitable questions up front: we need it to be able to adaptively choose questions that are tailored to the already-collected user responses.
We propose to address this challenge using the framework of sequential Bayesian experimental design (BED; Chaloner & Verdinelli, 1995; Lindley, 1956; MacKay, 1992; Rainforth et al., 2024; Sebastiani & Wynn, 2000), which provides model-based, information-thherrtiee mechanism for making adaptive design decisions, given a generative model of the experiment. Specifically, we show how the problem of interactive information gathering with LLMs can be formulated

---

Published as a conference paper at ICLR 2026
sequential experimental design problem with model derived from the LLM, wherein iterate between choosing queries by maximizing expected information gain (EIG) in a variable of interest and updating our belief's with the information from the received response.
We call our approach BED-LLM and show how its success is critically dependent on our precise model formulation, belief updating procedure and EIG estimation strategy. In particular, we show that it is essential to formulate the model with a precise distribution pairing that does not solely rely on in-context learning update belief's and uses the LLM's uncertainties in the space of answers rather than the more complicated underlying hypothesis space we are trying to learn in.
Together, we find that these innovations provide substantial performance benefits over directly generating queries from the LLM and more basic approximations of the sequential BED framework. Specifically, we first find that BED-LLM provides substantial improvements the success rate for the 20 Questions problem across a variety of LLMs and target quantities. On average, BED-LLM improves the success rate by 37.4 percentage points compared to direct prompting of the LLM, with the success rate more than doubling in over half of the setups considered and never decreasing. Second, we demonstrate noticeable improvements using the LLM for movie recommendations, showing that these benefits hold even when the LLM's predictive model differs from that of the answerer.
2 PROBLEM FORMULATION AND BACKGROUND
There are two natural ways to improve LLMs' ability to gather information: modifying the model itself (c.g. via finetuning) or altering how the model is used at deployment time. We focus on the latter, since cetemmatioongatherrie preferences), and deployment-time methods avoid the cost and difficulty of finetuning an LLM altogether and are applicable to any existing LLM. However, we emphasize that improvements the model level (e.g. Zhang et al., 2024) would be complementary to our approach.
tasks rarely provide task-specific data upfront (e.g. user's unknown
To formalize the notion of information gathering, we need concrete idea of what wish to learn about. We denote the target quantity of interest as 0, which may represent, for example, a user's preferences, the answer to a question, or a desired piece of content. We start with incomplete information about 0, as represented by an initial belief distribution or prior, p(0). but can refine these beliefs by making queries, I E X, to the user or some other external agent and receiving responses. E Y. that are informative about O. Multiple such queries, sequential decision Docision-mmakin making process where we iteratively choose each 24 based on the collected history, 14-1 == (I,, V/ E As our history grows, we will update our belief distribution to obtain p(0: 11) via some model updating procedure.' In the LLM setting, there is considerable flexibility in how p(0; h4-1) is constructed, as discussed in $3.1 and $4. While p(0; hT-1) need not be explicitly defined, it provides the foundation for our iiformation-thooreti method of query selection.
can be adaptively selected
For clarity of exposition, we focus on the case where the Ia correspond to explicit questions asked to the user, but emphasize that the approach applies more broadly to other forms of external interaction by the LLM, such as retrieving documents or calling external functions.
2.1 IN-CONTEXT UPDATING OF BELIEFS
natural and cheap way to incorporate the interaction history into the LLM to include it in the context (Brown et al., 2020). If the LLM's distribution over generated text, E Z, is PL.M((2) given appropriate prompting, then (2 h2-1) is an updated distribution with the previous question- response pairs in context. From this. we can derive an updated belief distribution over 9. Most simply, this can be done by using (1. h4-1) to directly query about (c.g. if 9 is some preference, we could prompt the I.M to predict this preference). However, as we show later, this approach often fails to appropriately incorporate the information from h leading to belief distribution inconsistent with past observations. This is consistent with recent work that shows that in context updating does not treat all contextual information equally (Kossen et al., 2024; Liu et al., 2024b; Zhang et al., 2024). In $3.1, we introduce more robust method for deriving p(0: h(-1).
We carefully distinguish between explicit probabilistic conditioning, i.e. p(a[b), and more general depen- dency, p(a; b). The former corresponds to the conditional distribution of an associated joint distribution, p(a, b). while the latter may not. Here, 14-1 influences our distribution on 6, but it is not derived via a joint distribution.
2

---

Published as a conference paper at ICLR 2026
2.2 INFORMATION- EXPERIMENTAL DESIGN
The core of the BED framework is a joint generative model, p(0, v),,, over the target quantity, 0. and the outcome, y, corresponding a design, x. Typically this is specified as Bayesian model using prior, p(0). and a likelihood, v)) In the general case, designs are chosen to maximize the expectation of some utility function, (8,, y. z)). under this model: we choose x² arg max, pp(0,y=)) [U y, æ]]. The most common choice is to take U y, x) = log p(0, yix) l(gp(0) log p(y; æ), where p(0) and p(y; z)) are the marginal distributions on 0 and y implied by our joint model and we have assumed that our current beliefs on are independent of the design, æ. This leads to an objective corresponding to the expected information gain (EIG) in 0 (Lindley, 1956; 1972),
EIGg (x) = H[p(()] - B) [H p ( g: x0]] = H[p(w; a)] E
e0) [H [Vv 0; x]]}
(2)
where H denotes the Shannon entropy (i.e. H[p(0)] p0) [lo p(0)). We can thus equivalently think of the EIG as (a) the mutual information between and y. (b) the expected reduction in entropy over 9 (i.e. information gain in 0) from observing data simulated from our model, or (c) the expected reduction in entropy over data from observing 0 simulated from our prior (Sebastiani & Wynn, 2000).
Working with the EIG is highly suited sequential or adaptive design approach, generally referred to as sequential BED or Bayesian adaptive design (Rainforth et al., 2024). Because the EIG is only a function of our underlying model, when we update the model as new data becomes available, our EIG design objective will naturally update as well. Specifically, to derive the incremental EIG (Cavagnaro et al., 2010) for the 1-th query, (TG he-1), we simply replace the joint in the above formulation, p(0, y; zr, with the updated joint, p(0, ye; 1e zt), with all marginals and conditionals derived from this (e.g. p(y; z) becomes p(y:; 1. D).. Here this updated joint conventionally comes from a Bayesian update of the original model. However, in many cases, this is not practical and other non-Bayesian updates are performed instead. For example, in active learning the update often actually corresponds to retraining the model with the new data (Bickford Smith et al., 2023; Gal et al., 2017).
3 SEQUENTIAL BAYESIAN EXPERIMENTAL DESIGN WITH LLMS
The sequential BED framework described in $2.2 requires two core components to be specified by the user: (a) an initial joint model, p(0, y; x), over hypotheses, 8, and outcomes, y, given design, x; and (b) a procedure to derive an updated model, p(0, ye: h, (,+)) ...), after observing h In the LLM setting, there is significant flexibility in these critical methodological decisions. In particular, there many ways to derive a suitable joint distribution from the LLM and its ability to learn in-context provides opportunities for update methods that go beyond standard Bayesian model updates.
Model construction A major challenge in the LLM setting is that unlike conventional probabilistic models, in general, PLLM (f) PLLM (3: [0, .=)) * PLLM (y: x) PLLM (9; [a. yl). That is, we induce a different joint distribution if we first sample then sample y with @ in context (which we refer to the prior-likelhhodd pairing) versus if we first sample y then sample O with y in context (data-estimation pairing). Moreover, we can deviate from the distribution directly induced by the LLM one or both variables. The success of using BED with LLMs turns out to be critically dependent on these choices.
We delay proper discussion of this complex issue until $4, where we will see that the preferable setup can depend on problem setting and, in particular, the relative complexity of spaces of 0 and y. For now, we will focus on using the prior-likelihood pairing; we will argue in $4 that this the advantageous setup in many practical scenarios. While we will generally use the LLM's directly induced distribution for the likelihood, we allow the prior to deviate from this in a mooblem-specife manner. As such, our initial joint model will be p(0, x) p())pp. (0, x:).
Model updating Optimally updating the joint model in this setting requires incorporating new observations in way that both fully captures the information from new data and is computationally tractable. At one extreme, we could target full Bayesian updates via approximate inference, as in classical sequential BED. However, this demands a prohibitively large number of LLM evaluations to accurately approximate the posterior, and it does not exploit the power of the LLM as a proba- bilistic generative model, where autoregressive sequential rollouts often lead to more nuanced and diverse behavior than repeated static queries. At the other extreme, simple in-context updating, with p(0: 11-1) PLLM (0; h1-1), is cheap but, as we show later, fails to reliably capture information
3

---

Published as a conference paper at ICLR 2026
from new data, leading to inconsistent belief states and undermining the sequential BED approach. As we discuss in $3.1, we therefore employ a strategy that is somewhere between the two: drawing samples in way that utilizes PLIM (8: h4-1) while encouraging diversity, then filtering out samples that are actually not compatible with h4-1 and renormalizing. We refer to the resulting distribution as (f; h2-1)- We do not update our likelihood model, PLLM (0; h4-1): comparison of updated vs. static likelihoods in our experiments, and a discussion.
App. F.3 for empirical
BED-LLM We now introduce our specific algorithmic approach, BED-LLM. Here, the queries will correspond to our designs, x (assumed to be in form of questions posed to the user in the following for simplicity, but could also be external function calling. document retrieval, web search, etc), and the responses received will correspond to our outcomes, y. Using the LLM to derive joint models over these outcomes and the target variable, 0, given the history, h4-1, as described above, we can interleave choosing informative questions by optimizing the incremental EIG, (IG, he-1), and updating our underlying model based on the received question respooss pairs. Specifically, BED-LLM iterates over the following key steps, where t indexes the current turn (see also Fig. 1).
(A) Extract belief's ($3.1), Use joint model p(0. yo; 11;h1-1, = p(f)PLLM(()) [0, mil), where hg 0, for t and p(0, ye: h1 = (f he-1)PLLM(()) [0, 2.)) fort 1.
(B) Generate candidate questions ($3.2). Propose candidate set of M diverse, multiple-choice questions, A'cand, by appropriate sampling of the LLM based on the history, h4-1-
(C) Estimate EIG ($3.3). For each candidate, Ze E Xeaand estimate EIG, (zy; ht-1).
(D) Select and ask the best question. Choose 24 by EIG maximization and pose to the user.
(E) Update the history. Observe response, y/. and update the history hr (h+-1, (Ne, Mc)).
3.1 PRIOR CONSTRUCTION AND BELIEF UPDATING
The Savage axioms (Savage, 1954) tell us that rational agent should update its beliefs in Bayesian manner. However, doing full Bayesian updates to our model as the history grows is generally impractical for computational reasons in the LLM setting, as it requires approximate inference and this, in turn, typically requires large numbers of expensive likelihood evaluations. Furthermore, the Savage axioms only hold if our (implied) prior truly represents our beliefs, but we find that PLLM (0) is typically heavily overconfident on a small number of possible hypotheses and can struggle to convey the full range of possibilities even with careful prompting and a high temperature (see Fig. 5).
A natural tractable alternative is to derive our beliefs through LLM in-context updates, that is, use (O; h,,1), ), noting that this has been shown to behave differently to Bayesian updating (Falck et al., 2024; Kossen et al., 2024). However, we find that even state-of-the-ard LLMSs such as GPT- 4o (OpenAI, 2024) often fail to incorporate history faithfully: they regularly sample hypotheses incompatible with past observations and exhibit premature overconfidence, with both issues becoming more pronounced as h grows. We discuss reasons for these shortfalls in App. A.3.
To avoid these shortfalls, we instead propose approach that balances tractability and faithfulness. Although we will still use PLLM (6; h1-1) as the basis for deriving our belief state over 0 (i.e. our intermediate prior), we make various alterations effectively incorporate historical information and ensure diversity. Our derived distribution, which we refer to as (0; 14-1), differs from PLLM((: hx-1) two key ways. First, we filter the generated hypotheses according to whether they are compatible with the history h--1. We do this by using the LLM to check the compatibility of each sampled 0 with all the previous inestioo-answern pairs in h (using PLLM((;; x,)) for i E (1, ... 1)) and then rejecting that sample if an incompatibility is found. Specifically, a sample is rejected if the likelihood of an observed answer falls below a predefined threshold, chosen to balance robustness to model uncertainty against the need to enforce strict historical coherence. To reduce the computational cost of generating and evaluating hypotheses, we further include a sopoohhsis-retenttiin mechanism: any hypotheses from the previous turn which remain consistent with the most recent question and observation are retained in the hypothesis set without regeneration.
Second, make number of modifications to promote diversity. Rather than generate candidates independently, we prompt the LLM to generate batches of candidates using prompt encouraging diversity. After filtering these candidates above and removing duplicates, then impose uniform distribution. Details of our exact setup for py (0; hz-1) are given in App. E.
4

---

Published as a conference paper at ICLR 2026
Current history: hg2 (("Born in the 20th century?", "Yes"), ("Is this person male?", "Yes")).
(A) Extract beliefs ($3.1). Construct hypothesis set @cand {0. 1. by sampling candidate hypotheses,
0 ~ PLLM(0;; (0;44) /2). and rejecting any 0 that is inconsistent with lt.. Use joint model p(0, yt he, x)
Py (0; (y: [0, æ]), where py (0; h2) uniform over @rand
Barack Ohama
Steve Irwin
Hugh Laurie
Banksy
Elvis Presley
(B) Generate candidate questions ($3.2). Sample ēI:M ~ PLLM [h--1, @rand).
51: "Was this person born Antarctica?"
82: "Was this person born in the 19th century?"
#3: "Is this person an artist?"
34: "Is this person European?"
āo: "Does this person prefer thrash metal over death metal?"
(C) Estimate EIG (83.3). Compute Hip(y: x[)]
n= H)PLLM(W: [o., zo ElG)(2;A2).
entrupy
expected eniropy
Question
Marg.
Exp. cond.
EIG
Intuition
T1 Born in Antarctica?
2 0
0
Answer "No" for all 6,
22
Born 19th century?
0
Redundant given h2
33
An artist?
0.56
0.41
0.15
Uneven split
54
European?
0.97
0.17
0.80
Balanced split; crisp answers
35 Thrash vs. death metal?
0.89
0.88
0.01
Uncertain even given 0
(D) Select and ask the best question. Choose 13 T. by maximizing EIG. Output this to user.
(E) Update the history. Observe answer, ys. Set hg (122, (Ira, ys)).
Figure I: BED-LLM applied to the 20 Questions game involves repeatedly constructing belief state, generating candidate questions, estimating and maximizing EIG to select a question, and interacting with the user gather data. The contrast between 34 and ãtş illustrates the benefit of using EIG with non-deterministic likelihood: ã5 has high marginal entropy (answers are uncertain), but its expected conditional entropy is equally high (answers are uncertain even given 0), nearly nothing is expected to be learned, and Fa should be favoured as a result. Numerical values are illustrative.
3.2 GENERATING CANDIDATE QUESTIONS
As it is not computationally feasible to directly optimize over the space of possible questions, we rely on using the LLM to propose diverse candidate questions, xeandd then select the best question from these. We consider specific approaches.
(a) Unconstrained generation: given h4-1. the LLM is simply asked to propose new questions by sampling from PLLM ht-1) with appropriate prompting. (b) Conditional generation: the LLM is given both h4-1 and generated set of hypotheses, @cand {0, } J such that we sample from (L [ (cand)); specifically,
the LLM is prompted for questions that "slice" the hypothesis pool into roughly balanced subsets.
For both strategies, we sample M questions jointly with relatively high temperature to encourage diversity. Conditional generation allows questions. However, it risks overfitting to caand In practice, we find it is effective for discrete spaces 1),.1), but less so for spaces with complex, overlapping hypotheses ($6.2). We restrict questions to multiple-choice format to simplify uncertainty quantification (see $4).
"guide" the LLM propose highly informative
3.3 ESTIMATING EIG FOR RACH QUESTION
To estimate the EIG based on Equation for given question æx, we use the following Rao- Blackwellized estimator based on the LLM's predictive distribution:
EIGg(Ie: 11-1) x N ΣN Eneyy (LLM [0n, æel) log PLLM (16; (On, 21])
- Emey M(ve:
log p(ve: [1
5

---

Published as a conference paper at ICLR 2026
where P(ye: (h-11.2,):== N En= (LIM(U: [6,, 2x]) and ~p h4-1) (see $3.1). This estima- tor has been used in other BED contexts (Gal et al., 2017; Rainforth, 2017). Note that the samples do not need to be independent for this estimator to converge, provided they satisfy some appropriate form of ergodicity or decaying correlation (see, e.g. Billingsley (2013)). When constructing this estimator, we compute the PLLM [en; terms using the L.M'' logits whenever possible. By the Rao- nho-Blacwwell theorem, this always produces lower variance than purely sample-based estimators (Rao et al., 1945), like those employed in Hu al. (2024) and Kobalczyk et al. (2025).
Avoiding deterministic likelihood assumptions Previous attempts to apply information criteria to choosing queries in LLMs have generally assumed responses are deterministic given (0, xr) (Cooper et al., 2025; Kobalczyk et al., 2025; Hu et al., 2024; Mazzaccara et al., 2024; Piriyakulkij et al., 2023). Under this assumption, the EIG simplifies to the marginal predictive entropy, H[p(ye: F4, hy-1)] )}
This is problematic as, in practice, the expected likelihood entropy will vary with zt.- In general, Ep(0: [ p(y: (8 ht-)]] measures how certainly the question can be answered once 0 is known. Including it in our objective is essential in avoiding questions that are irrelevant, ambiguous, unclear, or simply unhelpful in our quest to learn about 0. Fig. 1 illustrates this concretely-question T4 has high marginal entropy and low conditional entropy (answers are crisp given 0). yielding high EIG, while i5 has equally high marginal entropy but also high conditional entropy (answers are noisy even given 0), so the terms cancel and nearly nothing is learned. An entropy-only method would score both similarly and risk wasting a turn; the same failure mode causes the Entropy ablation to provide no improvement over Prompt-Only in our preference elicitation experiments ($6.2). Given that both terms of Eq. 3 are computed from the same LLM likelihood evaluations, retaining the full EIG requires no additional calls and provides no computational savings. Thus, we advise against making deterministic likelihood assumptions.
4 ON THE SPECIFICATION OF p(0, yes h4 1, 2,), AND ITS IMPLICATIONS
As we described in $3, successfully applying sequential BED in the LLM setting hinges upon how we specify, and update, the joint distribution, p(0, yt: 2e). In particular. as previously highlighted, there are two distinct ways to derive the joint model from our LLM: using a prior-likelihood pairing, p(0; h4-1) p(t:; [0, 244). ]) or a estimmattttnion pairing, p(y:; [b+-1, sza) p(0; T4, v:)). The first construction mirrors deriving our beliefs about 0 from conventional Bayesian posterior with a concrete prior and likelihood derived (at least partially) from the LLM, whereas the second has analogies to
pposteiir approach (Fong et al., 2023; Falck et al., 2024) in that it that samples hypothetical data and draws inferences on given hypothetical data using in-context learning. In our outlined BED-LLM approach, we adopted prior- likelihooo pairing. Below, we justify this decision and also discuss certain settings where the data estimation setup might be preferable instead.
Modeling flexibility The most obvious relative merits of the prior-likelhhood and cnttamsstimtion pairings are in the flexibility in how each term is chosen. The prior-likelihood pairing gives us greater flexibility to construct prior set of beliefs over 0 that is distinct the LLM's internal beliefs, it allows us to directly control this prior by changing p(0; h2-1), whereas the prior is only implicitly defined in the data-estimation pairing. In $3.1 we exploited this flexibility through our definition of (8; h) On the other hand, the data estimation pairing could provide some beneficial flexibility in specifying how the data itself is simulated through changing p(y:; [h z1]), which could, for example, be useful when we have access to external data simulators.
Faithfulness of conditional distributions While deviations from relying on direct LLM predictions are also in principle possible for the conditional models p(u:: [0, x:)) and p(0; [h.-1, Zt, 81 Ur)), in practice, these will typically be more difficult and expensive to implement. This is first because these conditionals need to be instantiated for each sampled instance of the conditional variable (0 and y/ respectively), rather than just needing us to set up single marginal distribution. Second, to construct estimators for Equations (1) and (2), require access to concrete probabilities for the conditional distributions (in order to calculate entropies), whereas we only needed to draw samples for the marginal distributions (in order to approximate expectations). As such, the conditionals need to be explicit distributions, or at least ones where the probability can be cheaply estimated, so they are more difficult to define through the output of some algorithmic procedure, especially in large spaces.

---

Published as a conference paper at ICLR 2026
When considering the conditional distributions, the decisive question the relative merit of the two formulations is which conditional factor we are willing to trust the LLM to supply as a f probability distribution. Critically, including, for example, tail behavior-not merely the fidelity of typical samples; the marginal factors, by contrast, only need to be sampled from. If accept the LLM's direct predictive distribution for p(yi; [0, zel). then we are basing our notion of uncertainty around (and will need to calculate) HPPLLM (ye: [0, 2z 3r)]] and if instead we place more faith in the LLM's internal distribution for p(0; [h,-1, F2, Vel), then we are basing our uncertainty around H H[LLLM (#;; [he-1, V++1l)] 1))- In essence, the choice between
rely on how the LLM captures uncertainty in this full distribution-
likelliid and data eattmmsstmation pairings thus comes down to whether we believe the LLM will produce more appropriate conditional uncertainty over 0 or y. along with our ability to numerically estimate this uncertainty cheaply.
This difference becomes particularly noticeable when the complexities of the spaces of f and y differ significantly. Our ability to draw sensible samples of either will generally be quite robust to these spaces being complex high-dimensional; this is where LLMs tend to thrive, effectively generating highly complex outputs in an autoregressive manner. However, evaluating the entropy of distribution becomes dramatically harder the dimensionality complexity increases (Acharya et al., 2019; Paninski, 2003), and the entropy of the predictive distribution of an LLM in such cases will not typically provide a sensible measure of uncertainty (Kadavath et al., 2022; Desai & Durrett, 2020). As such, the decision between joint formulations should predominantly be hased on the complexity of the space of f versus that of y: we should generally favor the prior-likelhhod formulation if 0 is more complex and the data-estimation formulation if y is more complex. For the problems that we consider, the space of y less complex than that of 0, indicating we should, in general, use the prior-likelihood formulation. However, in cases where this is not true, the data-estimation formulation may be preferable instead, see App. B for further discussion on this and on the choice of A.
Extracting the belief state A further advantage of the mnior-likelihooe construction is that our belief state on 0 can be extracted directly as py h4-1). With the estimaattnt construction, we would have to estimate the marginal on 0 by integrating P(u:: [ p(0; [h Tt, Ue!) over the syn- thetic response yt- Direct access to p(0; f4-1) is also important to ensure that our current belief state is independent of the next question Ie, which is both intuitively desirable and theoretically required to be a valid BED approach (Lindley, 1972); estimaaiionn formulations will generally violate this.
RELATED WORK
Several works have explored the baseline ability of LLMs to rapidly Iearn about a parameter of interest by asking questions (Zhang et al., 2024; Li et al., (ef2sb)-ffeccivell our Prompt-Only baseline in $6. While these works demonstrate some ability to adaptively construct seformationnseekinn questions, they often fail extract important information (Li et al., 2025a).
Some works have further specifically attempted to choose questions based on model-based uncertainty criteria (Piriyakulkij et al., 2023; Hu et al., 2024; Kobalezyk et al., 2025; Mazzaccara et al., 2024; Cooper et al., 2025). None of these works provide the same careful consideration of how the underlying joint model should be formulated, which underpins our own work, and they all assume deterministic likelihood models that mean their objectives correspond to sample-based estimate of marginal predictive entropy in practice, as explained in $3.3. In general, these previous works have also required restrictions the space of allowable hypotheses, I, and typically require additional assumptions and/or approximations. More extensive discussion of related work is given in App. C.
EXPERIMENTS
We now assess how well BED-LLM and alternative Cooommationggaheriiin approaches work in two practical scenarios: 20 Questions, a game in which the player has to guess a target entity and can ask up to 20 yes-no questions about the entity; and preference elicitation, task in which the agent has to predict a user's preference profile and can ask five multiple-choice questions to the user.
Answerer We produce answers to the questioner LLM's questions using separate answerer LLM. The answerer is provided with a ground-trute -tuth 8" (a target entity in 20 Questions or a user profile in pref- erence elicitation) and processes individual questions from the questioner without access to any of the questioner's 's context (i.c. h,- and the questioner's 's prompts). We test two questioner answerer where the two served by separate instances of the same I.M,, or two different L.MMs. The latter see-
guestioner-answerer setups,
7

---

Published as a conference paper at ICLR 2026
GP 1-40-mii
Qwan2.5 5-8
GPT-ko-mini
GPT-4o
Liam-33 3-70B
Misral-Large
Ower2 5-728
Qwen? 5-726
GoT-io
Swiress % Calbritis on Annmmall
100
100
100
100
90
0-
0-
Sucass %
103
Success M Things
80
70
70
80
50
60
0
0
20
20
Turn 2
Tur
Tum r
Tur
Turn r
Turn
Turn
Prompt-Only
Spli
RED-LLM
Entropy
Figure 2: Success rate 20 Questions: mean + standard error across 100 targets per dataset.
nario is important because in practice, the answerer will often follow different distribution than the questioner's 's internal model for reasoning about responses, thereby forming a model misspecification.
Baselines We compare BED-LLM against three baselines. Prompt-Only prompts the questioner to directly generate an informative next question, without explicit hypothesis generation or a acquiiiuuittoonn objective, and then sampling the question with temperature T 1; this was explored by Zhang et al. (2024). CoT augments Prompt-Only with a ReAct-style (Yao et al., 2023b) chain-of- of-thought: the LLM first produces thought (what has been established, what information would help most) then an action (the question). This tests whether structured reasoning alone can close the gap BED-LLM. Split chooses the question that most equally splits sampled set of hypotheses, @rand which corresponds to maximizing the marginal predictive entropy, H[p[y; Iz, ht-1)),, in model with a deterministic likelihood. As such, the methods of Cooper et al. (2025), Hu et al. (2024), Kobalczyk et al. (2025), Mazzaccara et al. (2024) and Piriyakulkij et al. (2023) can all be viewed as variants of this objective. To the best of our knowledge, Split represented the previous state-of-the-an method for 20 Questions. We note that our own specific Split baseline implementation, which uses BED-LLM's filtering mechanism, also achieves dramatically better results than reported by, for example, Kobalczyk et al. (2025), so this constitutes a strong baseline relative to previous work. On top of this, our implementation of Prompt-Only appears to significantly improve over that of Zhang et al. (2024). Additional evaluations and full plots in App.
6.1 20 QUESTIONS
We consider three sets of 20 Questions problems: Animals, Celebrities, and Things (See App. H.I). Each problem set comprises 100 target entities, {0: 1,100 The space of possible is large and not explicitly defined or restricted: we do not tell the LLM this set of target entities, so the space is bounded only by what the LLM can generate; by comparison, many previous works have relied on restricted spaces for (Chan al., 2025; Hu et al., 2024; Piriyakulkij al., 2023; Wang et al., 2025).
To evaluate performance, at each turn, E (0, 1...., 20). we extract 6 from (0, h2) using greedy decoding and we compute the success rate as the mean across of T( = 07) These evaluation guesses are not part of the questioner algorithm itself and are not included in h4- In line with the original rules of the game, we also introduce an explicit mechanism for the questioner to guess the answer one of its 20 questions: if the set of filtered hypotheses collapses to single candidate, the questioner asks "Is it (item)?". A correct guess ends the game; otherwise the negative response is added to h1-1 and counted towards the budget. See App. H for further experimental details.
BED-LLM improves over Prompt-Only and Split baselines Our results in Fig. and Tab. show BED-LLM significantly outperforming both baselines across all problems and L.MSs. Particularly notable is that BED-LLM's final success rate is typically more than double that of Prompt-Only. highlighting the substantial gains that can be achieved by using explicit EIG maximization.
BED-LLM ablations We further evaluate four ablations of BED-LLM to isolate the contribution of each of its core components; full descriptions are in App. G. Entropy replaces the full EIG objective with the marginal predictive entropy, H[p It, It=1)]; : it is similar to the Split baseline, but uses BED-LLM's likelihood model instead of a deterministic one. Pata--stimation swaps BED-LLM's
8

---

Published as a conference paper at ICLR 2026
Success Rate (%)
Model
Prompt-Only
Split
CoT
BED-LLM
Entropy
Data-Est.
ICL Beliefs
Impl. Max.
GPT-4o-mini
44.
78.42
55.50
88 133
1914.1
64118
18_39
47.15.0
GPT-4o
45150
83138
62.49
93126
88.133
70
25 4.
70146
Animals
LJama-3.1-8B
822.7
49250
19239
63249
54450
38249
25=44
16
LJama-3.3-70B
40:40
65448
40249
79:4.1
68447
40:49
33=47
54450
Mistral-Large
33:477
85436
35
95
83438
83443
53-50
53+4.0
Qwen2.5-72B
45+50
87434
51+
95-22
85+36
68+47
46-50
61+49
GPT-4o-mini
30:46
53150
42.550
72:145
55.50
32:47
16=37
31147
Celebrities
GPT-4o
45150
63119
63.14
86135
641488
55150
52:50
50.5.0
Llama-3.1-88
10#30
35+48
16+37
58+50
36+48
19439
24=43
19+39
Llama-3.3-70B
33447
43+50
36:48
55+50
46+5.
26+44
27=45
37+49
Mistral-Larg
19.10
63.199
42.550
91:22
68.14.7
66.148
31_47
36.148
Qwen2.5-72B
32.147
56.150
48..50
84.33
59.14.
34.148
26_4444
39.199
GPT-4o-mini
26.144
38149
33747
49.50
37.49
26
19_40
25
GPT-4o
34248
40:49
49250
64:44
49450
26244
19=39
42450
Things
1lama-3.
10:30
12:13
10230
26:444
15:16
9429
11=31
10:10
Llama-3.3-70B
34+48
46+50
35+48
55+5.0
48+-5.
19439
15-36
34+-48
Mistral-Large
26+44
51+30
29+46
58+50
52+5.
46450
19-39
30+4.6
Qwen2.5-72B
32147
51150
46150
62119
51150
39149
24
40149
Table I: Success rate (%) for Questions at the end of the game. Best result in bold. numbers show the standard error of the mean estimated using vp(1 - p)/(n 1) where p is the success percentage and is the number of datapoints. This estimator is positively biased and thus conservative.
Method
Joint model
Objective
Belief updates
BED-LLM
Prior-likelihodd
Full EIG (Eq.
Filtered (p²)
Prompt-Only
None (implicit LLM) Deterministic likelihood
None (implicit LLM)
Raw ICL (PLLM)
Split
Pred. entropy
Filtered (py)
Entropy
Prior likelliidl
Pred. entropy
Filtered (py)
Data Estimation
Data estimation
Full EIG
Filtered (p,)
ICI. Beliefs
Prior-likelhhood
Full FIG
Raw ICI. (PLLM)
Implicit Max.
Prior-likelihodd
LLM judgment
Filtered (py)
Table 2: Summary of how each method relates to BED-LLM's three core algorithmic components. Each ablation (bottom section) modifies exactly one component of BED-LLM, highlighted in grey
prior-likelihood joint model for a data-estimation pairing (see App. D), testing the importance of BED-LLM measuring uncertainty in y space instead of 0 space (see $3). ICL Beliefs omits our filtering procedure in the belief extraction (see $3.1). just using the, often incoherent, raw in-context beliefs (0; h+-1) instead of (0; 1)) Finally, Implicil Maximization replaces explicit EIG estimation with LLM judgment, drawing on the Tree of Thoughts (ToT; Yao et al., 2023a) intuition of reasoning over hypothetical futures: the model is presented with the same candidate questions as BED-LLM, but is simply prompted to internally reason and select the question it judges most informative, providing a lightweight alternative to explicit EIG estimation.
In Tab. 1 we that BED-LLM comfortably outperforms all alternative approaches. Notably, Entropy provides the strongest alternative, with performance slightly better than Split. The fact that Entropy performs much more similarly to Split than BED-LLM shows that the use of non-deterministic likelihood is beneficial predominantly changes in the marginal predictive entropy itself. The improvement of Implicit Maximization Prompt-only is also notable, given how cheap it is to run (see Tab. 3 for run time information).
allowing us to target proper EIG, rather than due to
Prior-likelihod outperforms data-estimation Our analysis in $4 is validated by our results: BED-LLM's prior-likelihood approach substantially outperforms Data-Estimation. Data-Estimation still outperforms Prompt-Oni Comptt-Oll,, but interestingly performs worse than Entropy, highlighting the importance of estimating uncertainty in the y space instead of 0 space here. These findings reinforce our claim that the choice joint-model factorization a critical algorithmic decision.

---

Published as a conference paper at ICLR 2026
Q: GPI 144--iin
Q: Qwen2.55 5-72
1-40-miy
G-1
Libma-33-700
Mistral-Lagge
Qwen2.5-722
4c-min
Mcon Fatin
4.0
4.0-
4.0-
4.0-
3.5-
3.5
4.0
3.5-
3.5
4.0
3.5
Tum
Prompt-Dely
BFD-IM
Fatraay
Figure 3: Mean rating across 10 film recommendations: mean + standard error across 200 users.
Rejection sampling and explicit EIG maximization key We also see how we produce beliefs over matters: deriving beliefs using simple in-context learning, as in ICL. Beliefs, lead to massive performance drops. Further, while BED-LLM's routines for sampling candidate questions and hypotheses are crucial, they alone are not sufficient: passing the samples to an LLM and prompting select the highest-EIG question, as in Implicit Maximization, works much less well.
BED-LLM is robust to questioner-answere mismatch Our results in Fig. 2 demonstrate that the benefit of BED-LLM persists even under model misspecification. This is important for applicability to real-world users, whose responses will follow a different distribution than the questioner LLM.
6.2 PREFERENCE ELICITATION
Unlike 20 Questions, in which 0 a concrete entity and most reasonable questions have clear answers, many real-world information-gatti gaathrrigg tasks involve more abstract targets and less predictable data generation. A key example is learning user preferences, where it may be difficult to explicitly define concrete closed set of possible 0, or for the LLM develop appropriate uncertainty estimates. To study such a scenario, we evaluate BED-LLM on inferring users' film preferences. Here the target 0 is somewhat abstract, and we have more flexibility in how we define our joint model. Our chosen setup is to define 0 to be a user profile, namely paragraph of text describing the user's film tastes with our answerer model prompted to emulate user with a given profile; see App. I for full details. We consider 200 ground truth profiles, {Ø, },200 which, as with 20 Questions, are never revealed to the questioner. Because Split is not applicable likelihood assumption is clearly unreasonable), we benchmark with the similar Entropy approach instead. We also note that data estimmestintionn setup completely unviable here due to the large space.
baseline here deterministic
At each turn, E (0, (0.1,,..,))) 5), the questioner uses h 1 to generate ten film recommendations. This list then rated in its to the user profile using an LLM-as-judge setup (Trivedi et al., 2024; Zhu et al., 2025). Specifically, the answerer scores each film on a scale of to 5 (in 0.5 increments), based on how well the film aligns with 8"; this score is output together with a brief justification to increase reliability. The films' scores not included in h4-1.
Our results in Fig. show that, while Prompt-Only seems to be a stronger baseline in this preference-eliciaatinn scenario than for 20 Questions, BED-LLM still able provide boost over both it and Entropy, producing higher-rated film recommendations. BED-LLM's benefit is most clear in scenarios where the questioner belongs a different model class the answerer.
CONCLUSION
In this work, have shown how effectively apply the framework of sequential Bayesian experimen- tal design (BED) to the problem of interactive information gathering with LLMs. Specifically, we have introduced BED-LLM, which provides specific, informationnthhoretii sequential BED approach that makes variety of carefully justified design choices in the joint-model factorization, belief updat- ing, and EIG estimation. Particularly central BED-LLM the likel-oo pairing with filtering of hypotheses for consistency with the history. BED-LLM is notably the first work that uses both this prior- likelihood pairing without making a deterministic likelihood assumption that causes the EIG to simply to just marginal predictive entropy. Together, these innovations lead to substantial performance improvements compared to previous approaches. The results thus confirm that principled EIG-driven strategies can yield substantial gains for interactive, multi-turn information gathering problems.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
DC is supported by the EPSRC CDT in Statistics and Machine Learning (EP/Y034813/1) an Oxford- Radcliffe Scholarship and an Oxford Al Fast Exploration grant. FBS is supported by the EPSRC Probabilistic AI Hub (EP/Y028783/I), TR is supported by the UK EPSRC grant EP/Y037200/1.
REFERENCES
Jayadev Acharya, Sourbh Bhadane, Piotr Indyk, and Ziteng Sun. Estimating entropy of distributions in constant space. In Advances Neural Information Processing Systems, 2019.
Gati V Aher, Rosa Arriaga, and Adam Tauman Kalai. Using large language models to simulate multiple humans and replicate human subject studies. In International Conference on Machine Learning, 2023.
Chinmaya Andukuri, Jan- Jan-Philipp Fränken, Tobias Gerstenberg, and Noah D Goodman. Star-gate: Teaching language models to ask clarifying questions. In Conference on Language Modeling, 2024.
Leonardo Bertolazzi, Davide Mazzaccara, Filippo Merlo, and Raffaella Bernardi. ChatGPT's information seeking strategy: Insights from the 20-questions game. In International Natural Language Generation Conference, 2023.
Freddie Bickford Smith, Andreas Kirsch, Sebastian Farquhar, Yarin Gal, Adam Foster, and Tom Rainforth. Prediction-oriented Bayesian active learning. In International Conference Artificial Intelligence and Statistics, pp. 7331-7348, 2023.
Freddie Bickford Smith, Jannik Kossen, Eleanor Trollope, Mark van der Wilk, Adam Foster, and Tom Rainforth. Rethinking aleatoric and epistemic uncertainty. In International Conference on Machine Learning 2025. URL https: hwtp//ppnneeie.eeeeeee net / for didcyddyyo d 9M1CROs5.
Patrick Billingsley. Convergence of probability measures. John Wiley & Sons, 2013.
Tom Blau, Edwin V Bonilla, ladine Chades, and Amir Dezfouli. Optimizing sequential experimental design with deep reinforcement learning. In International Conference on Machine Learning, 2022.
Brown, Mann, Ryder, Subbiah, Kaplan, Dhariwal, Neelakantan, Shyam, Sastry, Askell, Agarwal, Herbert Voss, Krueger, Henighan, Child, Ramesh, Ziegler, Wu, Winter, Hesse, Chen, Sigler, Litwin, Gray, Chess, Clark, Berner, McCandlish, Radford, Sutskever, and Amodei. Language models are few-shot learners. In Advances in Neural Information Processing Systems, 2020.
Daniel R Cavagnaro, Jay I Myung, Mark A Pitt, and Janne V Kujala. Adaptive design optimization: A mutual information-based approach to model discrimination in cognitive science. Neural computation, 22(4):8879905, 2010.
Souradip Chakraborty, Jiahao Qiu, Hui Yuan, Alec Koppel, Furong Huang, Dinesh Manocha, Am- rit Singh Bedi, and Mengdi Wang. Maxmin-rlhf: Alignment with diverse human preferences. In International Conference Machine Learning, 2024.
Kathryn Chaloner and Isabella Verdinelli. Bayesian experimental design: A review. Statistical Science, pp. 273-304, 1995.
Kwan Ho Ryan Chan, Yuyan Ge, Edgar Dobriban, Hamed Hassani, and René Vidal. Conformal infor- mation pursuit for interactively guiding large language models. arXiv preprint arXiv:2507.03279, 2025.
Yizhou Chi, Jessy Lin, Kevin Lin, and Dan Klein. Clarinet: Augmenting language models to ask clarification questions for retrieval. arXiv preprint 2tt::22055117884 2024.
Michael Cooper, Rohan Wadhawan, John Michael Giorgi, Chenhao Tan, and Davis Liang. The curious language model: Strategic test-time information acquisition. In Second Workshop Test-Time Adaptation: Putting Updates to the Test! at ICML 2025, 2025. URL https://
openreview net forum 1 B.....aa.n

---

Published as a conference paper at ICLR 2026
Shrey Desai and Greg Durrett. Calibration of pre- pre-trained transformers. In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu (eds.), Conference on Empirical Methods in Natural Language Processing, pp. 295-302, Online, November 2020. Association for Computational Linguis- tics. doi: 10. 10.18653/v1/ 1 2200://0122000mmmmmmmmmm22111 URL emn1p-ma 21/.
http///aaaaaaattaaaa/oaaa org/2020.
Fabian Falck, Ziyu Wang, and Chris Holmes. Is in-context learning in large language models Bayesian? A martingale perspective. In International Conference on Machine Learning, 2024.
Edwin Fong, Chris Holmes, and Stephen G Walker. Martingale posterior distributions. Journal of the
Royal Statistical Society Series B: Statistical Methodology, 85(5):135--1391, 2023.
Adam Foster. Variational, Monte Curlo and policy-bused approaches to Bayesian experimental design. PhD thesis, University of Oxford, 2021.
Adam Foster, Desi Ivanova, Ilyas Malik, and Tom Rainforth. Deep adaptive design: Amortizing sequential Bayesian experimental design. In International Conference on Machine Learning, PP. 3384-3395, 2021.
Yarin Gal, Riashat Islam, and Zoubin Ghahramani. Deep Bayesian active learning with image data. In International Conference on Machine Learning, pp. 1183-1192, 2017.
Kunal Handa, Yarin Gal, Ellie Pavlick, Noah Goodman, Jacob Andreas, Alex Tamkin, and Belinda Z. Li. Bayesian preference elicitation with language models. arXiv preprint arXiv:2403.05544 2024.
F Maxwell Harper and Joseph A Konstan. The movielens datasets: History and context. Acm Transactions on Interactive Intelligent Systems, 5(4):1-19, 1415
Marcel Hedman, Desi R. Ivanova, Cong Guan, and Tom Rainforth. Step-DAD: Semi-amortized
policy-based Bayesian experimental design. In International Conference on Machine Learning, 2025. URL https: /ppnneveeeeeeeeeeeeeeeeeee net/ http://wwww..eeefooooo/e//-----e
Takanobu Hirosawa, Yukinori Harada, Kazuya Mizuta, Tetsu Sakamoto, Kazuki Tokumasu, and Taro Shimizu. Evaluating chatgpt-4's accuracy in identifying final diagnoses within differential diagnoses compared with those of physicians: Experimental study for diagnostic cases. JMIR Form Res, 8:c59267, Jun 2024. ISSN 2561-326X doi: 10.2196/59267. URL https: /orrttoioiieeeeeee jmir. wtl.orrg////0 /204//2222//// /11///////6
Zhiyua Hu, Chumin Liu, Xidong Feng, Yilun Zhao, See-Kiong Ng, Anh Tuan Luu, Junxian He, Pang Wei Koh, and Bryan Hooi. Uncertainty of thoughts: Uncertainty-awaar planning enhances S information seeking in large language models. In Advances in Neural Information Processing Systems, 2024.
Xun Huan and Youssef M Marzouk. Sequential Bayesian optimal experimental design via approxi- mate dynamic programming. arXiv preprint arXiv:1604.08320. 2016.
Desi R Ivanova, Adam Foster, Steven Kleinegesse, Michael Gutmann, and Tom Rainforth. Implicit deep adaptive design: policy-based experimental design without likelihoods. In Advances in Neural Information Processing Systems, 2021.
Rune Møberg Jacobsen, Samuel Rhys Cox, Carla F. Griggio, and Niels van Berkel. Chatbots for data collection in surveys: A comparison of four theory-based interview probes. In CHI Conference on Human Factors in Computing Systems, CHI '25, pp. 1-21. ACM, April 2025. doi: 10.1 04.144//7006988.714133
URL http: / //tp://xxxxo dww.doi..oo..o..ooooooo 10. 001111//775595 3714128.
Saurabh Jha, Rohan Arora, Yuji Watanabe, Takumi Yanagawa, Yinfang Chen, Jackson Clark, Bhavya Bhavya, Mudit Verma, Harshit Kumar, Hirokuni Kitahara, Noah Zheutlin, Saki Takano, Divya Pathak, Felix George, Xinbo Wu, Bekir O. Turkkan, Gerard Vanloo, Michael Nidd, Ting Dai, Oishik Chatterjee, Pranjal Gupta, Suranjana Samanta, Pooja Aggarwal, Rong Lee, Pavankumar Murali, Jae wook Ahn, Debanjana Kar, Ameet Rahane, Carlos Fonseca, Amit Paradkar, Yu Deng, Pratibha Moogi, Pratecti Mohapatra, Naoki Abe, Chandrasekhar Narayanaswami, Tianyin Xu, Lav R. Varshney, Ruchi Mahindru, Anca Sailer, Laura Shwartz, Daby Sow, Nicholas C. M. Fuller, and Ruchir Puri Itbench: Evaluating ai agents across diverse real-world it automation tasks. In International Conference Machine Learning, 2025.
12

---

Published as a conference paper at ICLR 2026
Saurav Kadavath, Tom Conerly, Amanda Askell, Tom Henighan, Dawn Drain, Ethan Perez, Nicholas Schiefer, Zac Hatfield-Dodds, Nova DasSarma, Eli Tran-Johnson, Scott Johnston, Sheer El-Showk, Andy Jones, Nelson Elhage, Tristan Hume, Anna Chen, Yuntao Bai, Sam Bowman, Stanislav Fort, Deep Ganguli, Danny Hernandez, Josh Jacobson, Jackson Kernion, Shauna Kravec, Liane Lovitt, Kamal Ndousse, Catherine Olsson, Sam Ringer, Dario Amodei, Tom Brown, Jack Clark, Nicholas Joseph, Ben Mann, Sam McCandlish, Chris Olah, and Jared Kaplan. Language models (mostly) know what they know, arXiv preprint Xrxi 220702200.0.21,, 2022.
Greg Kestin, Kelly Miller. Anna Klales, Timothy Milbourne, and Gregorio Ponti. Ai tutoring outperforms in-class active learning: an ret introducing novel research-based design in an authentic educational setting. Scientific Reports, 15(1):17458, 2025.
Katarzyna Kobalezyk, Nicolas Astorga, Tennison Liu, and Mihaela van der Schaar. Active task disambiguation with llms. In International Conference on Learning Representations, 2025.
Jannik Kossen, Yarin Gal, and Tom Rainforth. In-context learning learns label relationships but is not conventional learning. The Twelfih International Conference on Leurning Representations, 2024. URL https: wwwoopeeeeiieee net forum? www.mniddd.PAAiaaooooooooo
Philippe Laban, Hiroaki Hayashi, Yingbo Zhou, and Jennifer Neville. Llms get lost in multi-turn conversation. XrXiv preprint arXiv:2505.06/20, 2025.
Sanguk Lee, Tai-Quan Peng. Matthew H Goldberg, Seth A Rosenthal, John E Kotcher, Edward W Maibach, and Anthony Leiserowitz. Can large language models estimate public opinion about global warming? an empirical assessment of algorithmic fidelity and bias. PLoS Climate, 3(8): c0000429, 2024.
Belinda Li, Been Kim, and Zi Wang. Questbench: Can Ilms ask the right question acquire information in reasoning tasks? arXiv preprint arXiv:2503.22674, 2025a.
Belinda Z. Li, Alex Tamkin, Noah Goodman, and Jacob Andreas. Eliciting human preferences with language models. In The Thirteenth International Conference on Learning Representations, 2025b.
URL /ttttp:://ppppreee net wwt./nertfrtit.e..
forum? id=T.wWwAggM..
Yubo Li, Xiaobin Shen, Xinyu Yao, Xueying Ding, Yidi Miao, Ramayya Krishnan, and Rema Padman. Beyond single-turn: A survey on multi-turn interactions with large language models. arXiv preprint arXiv:2504.04717, 2025c.
Lindley. Bayesian Statisties: Review. Society for Industrial and Applied Mathematics, 1972.
Dennis V Lindley. On measure of the information provided by experiment. The Annals of Mathematical Statistics, 27(4):98--1055 1956.
Jiayu Liu, Zhenya Huang, Tong Xiao, Jing Sha, Jinze Wu, Qi Liu, Shijin Wang, and Enhong Chen. Socraticlm: Exploring socratic personalized teaching with large language models. Advances in Neural Information Processing Systems, 37:85693-8572 2024a.
Nelson Liu, Kevin Lin, John Hewitt, Ashwin Paranjape, Michele Bevilacqua, Fabio Petroni, and Perey Liang. Lost in the middle: How language models use long contexts. Transactions of the Association for Computational Linguistics, 12, 2024b.
Chris Lu, Cong Lu, Robert Tjarko Lange, Jakob Foerster, Jeff Clune, and David Ha. The ai scientist: Towards fully automated open-ended scientific discovery. arXiv preprint arXiv:2408.06299 2024.
David JC MacKay. Information- objective functions for active data selection. Neural computa- tion, 4(4):590-604, 1992.
Indrajeet Mandal, Jitendra Soni, Mohd Zaki, Morten M. Smedskjaer, Katrin Wondraczek, Lothar Won- draczek, Nitya Nand Gosvami, and N. M. Anoop Krishman. Autonomous microscopy experiments through large language model agents. arXiv preprint: arXhv2500.10385, 2025.
Davide Mazzaccara, Alberto Testoni, and Raffaella Bernardi. Learning to ask informative questions: Enhancing Iims with preference optimization and expected information gain. In Findings of the Association for Computational Linguistics: EMNLP, 2024.
13

---

Published as a conference paper at ICLR 2026
Sewon Min, Xinxi Lyu, Ari Holtzman, Mikel Artetxe, Mike Lewis, Hannaneh Hajishirzi, and Luke Zettlemoyer. Rethinking the role demonstrations: What makes in-context learning work? arXiv preprint arXhh:2202.122837 2022.
Willie Neiswanger, Ke Alexander Wang, and Stefano Ermon. Bayesian algorithm execution: Esti- mating computable properties of black-box functions using mutual information. In International Conference on Machine Learning, pp. 8005-8015, 2021.
OpenAI. Gpt-4o system card. arXiv preprint arXiv:2410.21276. 2024.
OpenAl. OpenAl o3 and 04-mini system card. System card, OpenAL, April 2025. URL http://hh..ppaaalaoccoooooooo/// /ttp:m//ppa//22222272-2222222600 0a0----------0000---757222220220 pdf. Accessed 2025-07-15.
https://cdn... www.oo.e........................
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang. Sandhini Agarwal, Katarina Slama, Alex Ray, al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35: 27730-27744, 2022.
Lam Paninski. Estimation of entropy and mutual information. Neural computation, 15(6): 191-123, 2003.
Shishir G Patil, Huanzhi Mao, Fanjia Yan, Charlie Cheng-Jie Ji, Vishnu Suresh, Ion Stoica, and Joseph E. Gonzalez. The berkeley function calling leaderboard (BFCL): From tool use to agentic evaluation of large language models. In International Conference on Machine Learning, 2025.
URL https::///// wpenreview.eeeeeeeeeeeeeeeeoeee. net / fummm? id- 2GmDdhBdDk.
Wasu Top Piriyakulkij. Volodymyr Kuleshov, and Kevin Ellis. Active preference inference using language models and probabilistic reasoning. arXiv preprint arXiv:2312. 12009, 2023.
Tom Rainforth. Automating inference, learning, and design using probabilistic programming. PhD
thesis, University of Oxford, 2017.
Tom Rainforth, Adam Foster, Desi R Ivanova, and Freddie Bickford Smith. Modern Bayesian experimental design. Statistical Science, 39(1):100-1144 2024.
C Radhakrishna Rao et al. Information and the accuracy attainable in the estimation of statistical parameters. Bull. Calcutta Math. Soc, 37 1945.
Leonard Savage. The foundations of statistics. John Wiley & Sons, 1954.
Paola Sebastiani and Henry Wynn. Maximum entropy sampling and optimal Bayesian experimental design. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 62(1))145-1555 2000.
Prapti Trivedi, Aditya Gulati, Oliver Molenschot, Meghana Arakkal Rajeev, Rajkumar Ramamurthy, Keith Stevens, Tanveesh Singh Chaudhery, Jahnavi Jambholkar, James Zou, and Nazneen Rajani. Self-rationalizztion improves Ilm as a fine-grate fine-grained judge. arXiv preprint arXiv:2410.05499, 2024.
Jimmy Wang, Thomas Zollo, Richard Zemel, and Hongseok Namkoong. Adaptive elicitation of latent information using natural language. arXiv preprint arXiv:2504.04204 2025.
Shirley Wu, Michel Galley, Baolin Peng, Hao Cheng, Gavin Li, Yao Dou, Weixin Cai, James Zou, Jure Leskovec, and Jianfeng Gao. Collabllm: From passive responders active collaborators. In International Conference on Machine Learning, 2025.
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. In Advances Neural Information Processing Systems, 2023a.
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models, 2023b. URL https: /arxiv. org/abs 22..0..... 03629.
14

---

Published as a conference paper at ICLR 2026
Yizhe Zhang, Jiarui Lu, and Navdeep Jaitly. Probing the multi-turn planning capabilities of Ilms via 20 question games. In Proceedings of the Association for Computational Linguistics, 2024.
Yue Zhang, Yafu Li, Leyang Cui, Deng Cai, Lemao Liu, Tingchen Fu, Xinting Huang, Enbo Zhao, Yu Zhang, Yulong Chen, al. Siren's ss song in the ai ocean: survey hallucination in large language models. ACM Transactions on Information Systems, 42(2), 2025.
Lianghui Zhu, Xinggang Wang, and Xinlong Wang. Judgelm: Fine-tuned large language models are scalable judges. International Conference Learning Representations, 2025.
15

---

Published as a conference paper at ICLR 2026
APPENDIX CONTENTS
Discussion relating to $3
17
A.I Updating the likelihood
17
A.2 Estimating EIG for each question
17
A.2.1 Predictive entropy is not good approximation of EIG
17
A.2.2 EIG estimator
18
A.3 Prior construction and belief updating
18
Discussion relating to $4
18
B.1 An alternative view on the faithfulness of conditional distributions
18
B.2 Choice of 0
18
B.3 Alignment between EIG and belief updating procedure
19
C Extended related work
20
Datamaatioation method
21
D.I EIG estimation
21
D.2 Implementation
22
D.3 Generating candidate hypotheses
22
Generating candidate hypotheses for BED-LLM
24
Additional experimental results
25
F.1
20 Questions and Preference Elicitation
25
F.2 Wall-clock times
................................
25
F3 Effect of sequentially updating the BED-LLM likelihood
27
Further description methods and ablations
27
H Experiment details for 20 Questions
28
H.1
Problem sets
28
H.2 Evaluation
................................
30
H.3 Algorithmic details
30
I
Experiment details for preference elicitation
30
Ll Problems
30
I.2 Evaluation
30
I.3 Algorithmic details
31
Code Availability
16

---

Published as a conference paper at ICLR 2026
A DISCUSSION RELATING TO $3
A. UPDATING THE LIKELIHOOD
The success BED-LLM hinges on our ability update our joint distribution. As mentioned in $3, we choose not to update the likelihood model as more data is gathered, that is, our likelihood in the sequential setting will be PLLM (y:: [8, 24]) instead of PLLM (ye: [h,-1, 8, 22)). The main rationale of this choice is that for many problems our beliefs on A capture all the required information to predict y|æ, hence including the history is adding unnecessary context that could influence the LLM's behavior in undesirable ways. See App. F.3 for results comparison of static and updated likelihoods on the 20 Questions game. However, it is important to note that PLLM (yri [h 0, zzl) should be used instead for problems where & will not capture all information from previous data, e.g. if 0 is binary value corresponding to whether we reject a null hypothesis, or is the answer to a particular other question of interest.
A.2
ESTIMATING EIG FOR EACH QUESTION
Question 1
Question
Question:
Question:
Which ice cream flavor feels like the best match for this user?
Which film genre does the user most prefer?
Choose one option:
Choose one option:
Vanilla
A. Action
B. Dark Chocolate
B. Sci-Fi
C. Strawberry Swirl
C. Comedy
D. Mint Chocolate Chip
D. Horror
Predictive Entropy: Very High
Predictive Entropy: High
EIG:
EIG: High
Figure 4: Predictive entropy vs. expected information gain (EIG) in film-preference elicitation task. Left: very high predictive entropy (answer is completely unknown) but EIG 0 because the answer provides no insight into the user's film preferences. Right: both predictive entropy and EIG are high as the answer is uncertain, but different answers would lead to markedly different posterior updates, making it informative for learning film preferences. This thus demonstrates how the two criteria select different questions.
A.2.1 PREDICTIVE ENTROPY NOT A GOOD APPROXIMATION OF EIG
As discussed in $3.3, previous information-basee query selection mechanisms have assumed that responses are deterministic given 0 and æ. This implies that the expected entropy of the likelihood, Ep(0:h, 1) [H[p([(,))) 1 10; (t -4-1)l )]]. is constant over designs, meaning that maximizing EIG is cquivalent to maximizing the marginal predictive entropy, H[EEp(::h.,))PPl
z h-]1]]]-
In practice, the expected likelihood entropy can and will vary across designs. This variability in the expected likelihood entropy can be crucial in selecting good designs. A conerete example helps highlight how predictive entropy can differ significantly from EIG. Fig. 4 shows two candidate questions that could be asked elicit film preference. Question has high predictive entropy: in randomly selected group of people, we would expect high variation in ice cream preference (regardless of the individual's film preferences). However, since ice cream preference unrelated to film preference, the answer would not help narrow down our hypothesis space, and the EIG is zero.
This is also supported by evidence in our experiments ($6). Both the Split baseline, and the Entropy ablation, assume a deterministic likelihood; in particular, the Entropy ablation uses the same estimator of the predictive entropy as BED-LLM. In both cases, we see the performance significantly degrades relative using the full EIG. Further, omitting the expected likelihood entropy term provides meaningful computational saving- the same LLM evaluations are used for the top and bottom lines of Eq. 3, hence doing the full estimate of the EIG requires additional L.L calls to be made.
17

---

Published as a conference paper at ICLR 2026
A.2.2 EIG ESTIMATOR
One might be tempted replace p(y++1; [|t-1, ([++]) with PLIM(YC+1; (++11, in the EIG estimation in Eq. 3, as the two essentially offer alternative predictive distributions for the outcome. We also advise against this, though, noting that it again provides no meaningful computational benefits (unless one also assumes a deterministic likelihood, but this would then mean we no longer consider 0 at all). A key reason for avoiding this substitution is that would mean we are no longer estimating a true FIG: the inconsistency between the likelihood and the marginal data distribution means there is no longer a joint model where we are minimising our expected uncertainty in O. We also find that the LLM process of sampling 9 from py (0; h followed by y from (L [0, zx.)) tends to give better uncertainty over responses than sampling directly from PLLM (36+13 [/e-1, T++1l).
A.3 PRIOR CONSTRUCTION AND BELIEF UPDATING
In $3.1, we argued that Prompt-Only in-context updating is not sufficient for updating our beliefs: We fail to fully incorporate the information from the history he, and we often have overconfident distributions. The shortfalls of in-context learning in such settings have also previously be noted by, for example, (Liu et al., 2024b; Zhang et al., 2025; 2024). We posit two reasons why they likely struggle in such settings. First, the information from the different examples in the history are generally highly distinct in these informmaionn-attheinng settings (indeed, this is part of our aim in adaptively design informative questions), making it harder for the LLM to appropriately reconcile all the provided information than in many other uses of in in-context learning. Second, 0 will often represent a user-specific variable that cannot casily be predicted from any data other than the user's responses to questions: it has been argued that much of the success of in-context learning in LLMs is down to improving problem specification and linking the requested task to data it has seen in its training, rather than truly "learning" from the provided examples (Min et al., 2022; Kossen et al., 2024), but the history in our setting is rarely helpful for this due to its user-specific nature.
B DISCUSSION RELATING TO $4
B. AN ALTERNATIVE VIEW ON THE FAITHFULNESS OF CONDITIONAL DISTRIBUTIONS
Another way of viewing the distinction between the likelline and esttmmmtttttionn construc- tions is in which of the EIG forms, Eq. 1 or Eq. 2, we center our reasoning. For a given joint model, the two are, of course, mathematically equivalent. However, they give us different ways of thinking about what it means to maximize the FIG: reducing entropy in @ from seeing y, or reducing entropy in y from seeing 0. This, in turn, gives us a way to reason about how appropriate our joint model is. reasoning
When we choose to use one of p(y:; 10, zx)) or p(0; [ft-1, Vr]). we centering around the entropy of this quantity making sense, while allowing the other entropy in the other form to be implicitly defined from the resulting joint distribution; because the two forms are equivalent, we know that if our explicit form is suitable/unsuitable, the implicit form will be as well. If, for example, we directly fix the form of p(0; [h,- vi, wel) using our LLM's predictive distribution, we are also directly relying on its expected entropy being a meaningful measure of design quality. If 0 is -ighenimensional and predominantly free-form, the resulting entropy produced by the LLM is unlikely to be meaningful and using the data estimmmstittion pairing is unlikely to produce an effective strategy. However, if y is instead quite constrained, the LLM can produce a meaningful entropy over it, and choosing a model based on the meaningful distribution, and thus entropy, on O. Conversely, if is constrained and y is free form, the opposite will hold instead.
pairing is likely to implicitly define
B.2 CHOICE OF 0
An important corollary of this reasoning is that it can be important to be careful in our choice of exactly what we take to be, especially if we are using the data-estimation formulation. In particular, it is essential for entropy in the space of 0 to form meaningful notion of uncertainty, even if this entropy is not being measured through the LLM's predictive distribution of 9 directly. Thus, while 0 inherently represents what we are trying to learn about and should always be set up as such, if there is flexibility in how exactly we formulate it, we should be careful to choose form that yields
18

---

Published as a conference paper at ICLR 2026
an appropriate uncertainty measure. For example, if the LLM is trying to clarify what code user wishes it to generate, we could either choose to be the code itself or, following (Neiswanger et al., 2021; Bickford Smith et al., 2023), the output the code produces. Here the entropy over code outputs induced by our distribution on code is likely to be a much better measure of uncertainty than the entropy of the raw code itself, given that there multiple ways one can code the same operation.
B.3 ALIGNMENT BETWEEN EIG AND BELIEF UPDATING PROCEDURE
If our ultimate goal is to minimize uncertainty in 0, as measured by its entropy, then we can use the expected uncertainty reduction framework of Bickford Smith al. (2025) provide insights into how well our EIG formulation and belief updating procedures align. To simplify discussions, for now we consider the setting where we choose a single question r and obtain a response y. Following Bickford Smith et al. (2025), we can think of the "true" optimal design as selecting
Ferue- arg min Bpr. [H[(O:: xr, y)ll.
where Purue (y: x) is the true response distribution and p(0; x. y) is our belief state after the experiment.
Note here that true optimal design has direct dependency p our current beliefs about 0; it only depends on Ptrue (y: z) and the hypothetical beliefs we produce for given observed data, p(0; x, y). Thus, we can now that choice of joint model corresponds to different choices for approximating these quantities. Assuming that the LLM distribution is used directly for the conditional as per $4, we thus have that
the prior-likelihood pairing corresponds to using the approximations Perue (vF, Rs f p(0)ppLLM [0, 2))d and 10; v) p(0)ppaM(( (0,=))/ J p p(O)plaMy ())x)))00 and the data-estimation pairing corresponds to directly specifying a model for Perue (y; and then using the approximation p(0: z. y) = PLLM (0: [z. vl).
The appropriateness of each of these options, therefore, comes down to how faithful these approxima- tions are respectively the true data distribution, Purue x). and how we actually derive our belief distribution on 0 in practice once we have seen the new data.
The former of these considerations is difficult to control for as we simply do not know the true response distribution and it is hard to say which approach will thus estimate it best (though we can refer to the discussion in $4 determine which best matches our beliefs about the true response distribution). However, we do know upfront how we plan to derive our belief distribution on 0 in practice, so we can use this to guide which joint model we formulate our EIG from. Namely, we observe that (a) using the prior-likel likelhooo EIG pairing equates to assuming update to our beliefs on f using the likelihood PLLM [0, x)), and (b) using the data estimation EIG pairing equates to assuming p(0; x. y) as PLLM (6; [x. y))-
will make Bayesian
will make an in-context update our beliefs 0, are treating
Our preference between the pairings should therefore be guided in part by how we plan to update the model in practice. In particular, if we plan to make pure Bayesian updates, then the prior-likelhoodd formulation will tend to yield an EIG that is more faithful to our updating procedure, while if we only make simple in in-context updates, the data estammssimation formulation will tend to yield a more faithful EIG instead.
The update we use in practice, namely taking p(0; xr 3) = (O; [x, v)) as outlined in $3.1, can be seen being somewhere between the in-context and Bayesian updating: we initially sample from PLLM((: [z. yl). but then perform filtering and other steps. The relative extent to which it resembles each will be problem deppndenn and again be linked to how much we trust the LLM to capture uncertainty in the space of 0 vs. y.
For the settings we consider, we expect py (f: [x. vl) to generally be better approximated by Bayesian update than an in-context update, aligning with our decision to use the prior-likelihood formulation. The reasons for this are that a) the filtering often removes a large proportion of the generated samples, especially at later experiment turns, with PLLM (0; h1-1) not fully incorporating information from the history; b) the maintaining of the set of one consistent hypotheses from one turn to the next encourages more Bayesian behavior, with samples persisting unless contradicted by new likelihood term; and c) the typical premature overconfidence of PL.M (0; h to a small number of hypotheses means is typically unrepresentative of our beliefs.
19

---

Published as a conference paper at ICLR 2026
These theoretical benefits perhaps secondary the more practical benefits from the ease of constructing an appropriate model in the prior-likelihan formulation and avoiding direct uncertainty estimation in the space of 6. Nonetheless, they help confirm that our choices have not induced unnecessary mismatch between the EIG formulation and our updating procedure.
The picture here can get a somewhat more complicated once we move into the sequential BED setting. Here, our ultimate aim is actually to minimize H[p(β; hr]] at some final future horizon T. Now, we only care about intermediary belief states p(0; he) through their aid in future decision making toward the goal of minimizing the final entropy. Thus, even if we are working with in-context updates, it might be the case that p(e; he) only starts produce a meaningful entropy once we have seen enough data to sufficiently narrow down the possibilities on 0. The optimal behavior in such settings would be to learn a policy that directly targets this final belief state instead of sequentially targeting the incremental EIGs. However, this will typically not be computationally feasible in practice and we instead need to resort to a myopic prior-likelihood formulation in such myopic decision making settings, even if we are sequentially updating our beliefs on 0 through in-context updates, if this allows us to better guide the sequential decisions towards our final objective. The coherence of Bayesian updating means that the converse is unlikely to be true, so this provides further evidence towards using the erior-lieelhhod formulation.
cecision-making strategy. might thus still be better to use the
C EXTENDED RELATED WORK
Information-base question answering with LLMs Several recent works have (explicitly or implicitly) looked at information gathering with LLMS.. Most of these can be framed in BED setting, with a deterministic likelihood (Piriyakulkij et al., 2023; Hu et al., 2024; Kobalczyk et al., 2025; Cooper et al., 2025), and can be seen as variants of our Split baseline. Piriyakulkij et al. (2023) use a deterministic 0/1 answer likelihood p(a(x, q) via the LLM to prune items from pre-enumerated finite set given candidate question q. The question is selected by minimizing expected posterior entropy. They model user preferences with a binary ground truth, which would not be applicable in wefereecc--llcitattin deterministic likelihood to minimize entropy over finite set Ω in closed-world setting. Kobalczyk et al. (2025) target ambiguous task specifications in open-ended generation tasks by sampling a set of hypotheses (placing uniform prior over them) and viewing each question as a deterministic partition over those samples, looking for questions that split the samples roughly evenly. Cooper et al. (2025) compute posterior entropy over working set of top l hypotheses (without filtering) through heuristic pruning.
scenarios with nebulous user profiles. Similarly, Hu al. (2024) use a
Wang al. (2025) avoid the pitfall of deterministic likelihoods. They data eetiimttttitiinn framework to estimate EIG, focusing on scenarios where the target can be expressed as a predefined series of multiple-choice questions. Their approach relies meta-training a predictive language model on historic question/answer pairs, and so is not directly comparable with BED-LLM which requires no additional training or data. Chan et al. (2025) do not model likelihoods or posterior beliefs, instead they rely on the expected size of conformal prediction sets as a surrogate uncertainty metric. This requires the use of an additional calibration dataset, and is confined to closed- wooldd settings with a finite label set and pre-defined queries.
Post-training LLMs for improved information gathering Rather than augmenting a frozen LLM with the ability to estimate utility functions, some works have instead aimed to post-train an L.M to improve its ability to ask questions (Zhang al., 2024; Wu al., 2025; Andukuri et al., 2024). Most do not explicitly consider informativeness of questions: Zhang et al. (2024) and Wu et al. (2025) use reinforcement learning techniques to reward generations that quickly lead to the correct answer, and Andukuri et al. (2024) builds on Li et al. (2025b) by fine-tuning et al. (2024) do indirectly incorporate uncertainty, also using a deterministic likelihood: they use predictive entropy to identify informative questions, and then either fine-tune the highest-entropy question, or perform DPO comparing the highest-entropy question with a lower-entropy question. We do not address fine-tuning in this work, focusing instead on exploring the correct way to formulate BED using LLMs.
successful traces. Mazzaccara
Combining LLMs with parametric models As discussed in $4, a key challenge in adapting BED to the LLM setting is in aligning the expected information gain with the actual uncertainties extracted from the LLM after updating. Handa al. (2024) take different approach this problem by using
20

---

Published as a conference paper at ICLR 2026
Algorithm 1 Pata--ssimation sequential information gathering
Require: LLM history hn 2, budget T, num. hypothesis samples M xt
1: for 1= l,.., do
2: Generate candidates: sample Aeand = {x) (1) ,(..,,(()) (K) from p(zri
3:
for each candidate 2e Reaud do for each y E y do
4:
II enumerate answer options
5:
wy 5 ply: (1]-
Il answer prob. via LLM logits
6:
Sample {0th) m== ~ p(0; 11 vl)
LM
Estimate Hy - Híp(0; [14-1, yMM using (0(x)
7:
8:
end for
9:
Heond + EYEy wy Hl
I/ Term 1: marginal entropy of 0 (design-dependent) // samples from mixture
10:
Pool: {0m J= t ->yey(oM)
11:
for m 1, I..... M' do
lm log E Wy p(0m: [1 Fz, vl)
end for
Hmarg t- 1 M Em=1 fm
14:
15:
EIG(xx) +- Hmarg Hoond
16:
end for
17:
Select: 27 +- arg maxa, EIG(2:)
18:
Ask and observe: pose 27, receive Ve, set h1 (he-1, (x7,
19:
end for
the LLM generate features for external conventional Bayesian joint model (in their case, linear Bradley-Terry model), rather than deriving their joint model more directly from the L.M itself. This can be good choice when the problem is well-bounded and we already have well-specified Bayesian model form for the problem at hand; however, this may be challenging in arbitrarily large and complex hypothesis spaces. In particular, their specific method not applicable more widely beyond the preference learning context they consider.
BED has been noted that the traditional sequential BED approach can sometimes be suboptimal in practice, as it only optimizes the EIG of the next observation, without planning ahead for the fact that design decisions taken a given step can also influence the achievable EIGs from future steps (Foster, 2021). A variety of bascey-baeed BED approaches have subsequently been proposed to address this (Foster al., 2021; Ivanova et al., 2021; Blau et al., 2022; Huan & Marzouk, 2016; Hedman et al., 2025), while also removing the need to make model updates and conduct optimizations during the experiment itself. Our findings are complementary: by providing more faithful model factorizations, belief updates, and EIG estimators in the LLM setting, BED-LLM could supply stronger building blocks for policy-based methods, reducing variance, enhancing effectiveness, and improving the sample efficiency of policy training.
D DATA-ESTIMATION METHOD
Our Duta-Estimation method is based on model derived from data-estimation pairing ($3).
p(0, 1 xx) p(ue (x)] p(0; [he-1, we))
(5)
D.1 EIG ESTIMATION
Using the form of the EIG given by Eq. we have
(xG = Híp(0: /4-1, x)
Exwelhh [H [p(O; [he-1, v=l)]]
(6)
expected posterior entropy Crucially, the marginal on implied by this pairing is obtained by integrating out y:
marginal entropy of
p00 2) = Σ plvei 1, p(O; [/r-1, Nz, yel)
21

---

Published as a conference paper at ICLR 2026
which is mixture distribution whose components and weights both depend Unlike in the prior- likelihood pairing, where the belief state Py(0; ht-1) is constructed independently of the candidate design, the marginal entropy H[p(0; - 2)] here varies across candidate questions and cannot be dropped from the optimization. This is a concrete manifestation of the issue identified in $3: the data eattmestimation pairing does not provide design-indepenndnt belief state on 6.
Discrete answer space. When the possible values for are discrete (and finite) and we can evaluate p(ys [A,- I, æx]) in closed form, both terms of Eq. can be computed directly. The second term (expected posterior entropy) is:
Banesh 1.2.)) 1==.)) ((p 1, V.DIl
Σ plus [h,-1, x,)) H(p(O: [h,-1, Tt. yel)l. 3t
(8)
where each posterior entropy H[p(O; [h+-1, Del)] can be evaluated from the LLM's logits if these are unavailable, estimated by sampling. The first term (marginal entropy) requires evalu- ating p(0; 2)) as the mixture in Eq. 7, then computing its entropy. In practice, this entropy cannot be obtained closed form and must be estimated. A natural approach is to draw samples Om >>(0; 4)) (by first sampling Vm p(yi [1--1, #1)), then On ~ p(0; [he-1, Mel) Vm.) and using a plug-in or nearest-neighhor entropy estimator, or evaluating log p(0m: ht-1, p(0mi [/4-1,2 2, v)) exactly by enumerating over y.
log E, p(yt: [+,)
Monte Carlo estimator. When y cannot be enumerated, both terms must be estimated by Monte Carlo. Drawing N samples yo ~ p(ys [1,-1, )r)), , the full estimator takes the form:
N
N
EIGa(z;h,-i) so H
Σ 1=1
p(0: [h,-1, ynl)
Hip(O: J.NII (9)
N
==1
Whereas Eq. performs this computation over the answer space Y' (which is small and enumerable for multiple-choice questions), Eq. requires it over the hypothesis space O. For the first term, evaluating the mixture entropy requires computing (0; [,,-1, 2, ynl) for set of sampled values across all N mixture components over the full hypothesis text.
((M N) cost in autoregressive probability evaluations
D.2 IMPLEMENTATION
We provide an overview of the Data-Estimation procedure Algorithm 1. our experiments, answer space y is enumerable (multiple-choice options), the first term, we estimate the marginal entropy by sampling values from the mixture in Eq. 7 and evaluating log p(0; 1, 2)) by enumerating y; that is, use:
Eq. 8 for the second term. For
1
Σ
log
Ep(ur xx)) p(8mi 1,, m.,.),))))))))) el)) V
(10)
M
where 8m are drawn from p(0; 1.). This requires M x [ evaluations of pf [ x. vl) per candidate question, each involving full forward pass over the hypothesis text.
D.3 GENERATING CANDIDATE HYPOTHESES
To generate candidate values of for the data cattamsstinttin method, use the prompt in Fig. 6.
Fig. 5 shows an example of the distribution of samples obtained following two rounds in the 20 questions game. Note that the samples are highly concentrated just a handful of answers. This lack of diversity shows that the model's 's belief distribution is far more concentrated relative to the variability over valid hypotheses in the ground-truth task distribution, which negatively impacts the performance of the aata-estimmaion method.
22

---

Published as a conference paper at ICLR 2026
Conversation History (D)
Q: Ts this person known for their contribations to science? Is this person known for their contribations arts?
A: No.
A:
Sampled Hypothesis Distribution
van Gogh
Salvador Dali
Frida Kahlo 37
Georgia Koeffe
August Wilson 8
Auguste
Figure 5: An empirical hypothesis distribution generated by the LLM, conditioned the conversation history (top). By independently sampling N = 200 hypotheses, we observe significant mode collapse; the probability mass heavily concentrated overconfidence negatively impacts the performance of the data-esting eata-estimation baseline. Note that this aggregated view is purely diagnostic; Algorithm operates directly the probabilities of individual samples.
few prominent figures (e.g.. Vincent van Gogh). This
Figure 6: Prompt for generating hypotheses (and evaluating their probability) for the data- estimation method.
Return only the full name of one randomly selected Famous person (living or deceased) consistent
questions answers above.
increase zandomness:
of diverse and representative individuels. 2. Avoid defeulting to the mest globelly ubiquitous celebrities or femous figures.
Internally brainsterm
Output rules:
output person's a name spaces, capisalization ascental, mothing else.
extra words, explanations, numbering, or punsouation beyond what's in the name itself tbyohens//postrroies alloved if of the name).
Fig. 7 shows an example of in-context belief updating failing to respect the conversation history. The response the first question indicates that the target is male; however, after the second question, the LLM generates two female candidate hypotheses.
Figure 7: An example of in-context belief tracking with GPT-4o-mini proposing hypotheses inconsistent with the history.
Q1: Is the person male? Answarer: Yes.
Q2: Is this person oftea associated with eivil rights oz social justice?
Answerer: Yes.
Sampled hypotheses: I'Jamne Baldwin', Philip Rendolph', 'Angela Davis', "Melcolm x /W.E.B. Du sois', 'Desmend rutu', 'cesar Chavez', "Rosa Packs', , 'Martin Lucker King Jr.', "Langttnn Hughas', Lewis', 'Fraderick Dougloss', Thurgood Karahall', "Bayard Rustin']
Mandela',
sypotheses rejected with filtering:
[' ('Angela Davis', "Bosa Parks']
23

---

Published as a conference paper at ICLR 2026
E GENERATING CANDIDATE HYPOTHESES FOR BED-LLM
Figure 8: Prompt for generating candidate hypotheses for the "Things" dataset. Similar prompts were used for "Celebrities" and "Animals".
You are playing game of 20 Quastions. Using all of the questions ona and answers far:
Generate to (nun_samples) candidate entities that satisfy evecy clue. Each candidate must be a single, self-contsined entity (e.g.. "suropa", "sagpipe", "Diaden"),
List each entity on its own line no numbering, puastuation, or extre. text. Produce varied set by identifying features not implied by cluss and diversifying a allong them.
not repeat any eatity.
Return only the list of entitiss.
A fundamental challenge for BED-LLM and its ablations is generating sufficiently diverse set of candidate hypotheses from the LLM's belief distribution, that are consistent with the previously- answered questions. Below, we detail the steps we take to construct our distribution over hypotheses.
Candidate hypotheses are generated jointly, rather than independently As illustrated Fig. the distribution (6) is highly overconfident, often concentrating mass only few high- likelihood hypotheses. Thus, is not practical to directly use the LLM's ' distribution as a prior p(0). Instead, we jointly sample candidates 0 and assume uniform distribution over them. We can view this as sampling As from a mixture distribution. The LLM is prompted to generate a list of N hypotheses in single rollout, which corresponds drawing from the autoregressive list distribution
N II ! hel).
(f ...., o ;h))))
We diiversity-encorrggin prompt We use prompt designed to elicit stratified hypotheses by encouraging the LLM to consider different semantic features (e.g. age groups, genres, or categories) and implicitly diversify across them. An example prompt is shown Fig. In our generation prompt, we reverse the order of the question-answer pairs in he to place the most recent question at the top of the context window (while retaining earlier exchanges), ensuring that specific constraints are prioritized and mitigating context drift. For the 20 Questions experiments, we used a higher- than-normal temperature (T 1.3) to increase diversity of responses. For the preference elicitation experiments, we used T to obtain more coherent responses.
Candidates are filtered based on the history For each candidate, we use PLLM h2-1) assess whether it is compatible with the previous question/answer pairs. We filter responses where the probability of the given answer falls below a certain threshold; in our experiments we set this threshold to 0.2.
Valid candidates from previous generations are included We also filter the candidate hypotheses from the previous generation, based on the most recent question/answer pair, and include these in candidate set. We repeat the generation process, keeping the previously generated and filtered samples in context to elicit new generations, either twice three times if sufficient hypotheses have not been generated (noting the number of possible valid samples can be less than the number requested).
We define uniform prior using importance sampling, in practice we choose to not rely on the model's internal probabilities. Instead define the prior uniform distribution:
hypotheses While could in principle reweight candidates
Pf hz) Rd
6g.
Finally, we note that different LLMs respond differently to strategies aiming to increase diversity: some benefit more from higher temperature while others benefit from more repetitions of the sampling-iltering filtering cycle. For fairness, in our experiments we have kept these parameters constant across models.
24

---

Published as a conference paper at ICLR 2026
F ADDITIONAL EXPERIMENTAL RESULTS
F.1 20 QUESTIONS AND PREFERENCE ELICITATION
Animals
Celebrities
Things
Sucues
50
Tum
Tum
Prompt-only
Split
BED-LLM
Entropy
Data Est
[CL Beliefs
Impl. Max.
Figure 9: Success rate 20 Questions with Qwen2.5-72B, extended to 50 turns: mean + standard error across 100 targets per dataset. BED-LLM remains the best- rest-performing method at every turn. The performance gap baselines narrows in later turns the task saturates most methods eventually solve the easier instances - but BED-LLM consistently retains its advantage.
EG
5
10
15
20
25
30
35
10
15
50
55
50
65
70
75
80
[0]
Q1
Q2
Q3
Q4
Q5
Figure 10: Analysis of empirical convergence the Rao-Blackwellized EIG estimator using GPT-4o-mini. We plot EIG estimates for 5 candidate questions turn 5 of the 20 Questions game with 6* ="Saoirse Ronan", as a function of the number of samples in the hypothesis set e.
Fig. 10 shows the EIG estimates for five candidate questions the number of hypothesis samples [0] increases, at turn 5 of a representative 20 Questions game. The estimates converge rapidly with the number of samples, and more importantly, the ranking of candidate questions stabilizes well before the estimates themselves have fully converged. By [ = 10 the relative ordering of all five candidates already matches the ordering observed at [0] 85. This means that the question selection which is what matters algorithmically, since we only need the arg max, not the absolute EIG value-is robust to using small hypothesis set. This justifies BED-LLM's use of moderate sample budget without sacrificing decision quality.
F.2 WALL-CLOCK TIMES
Tab. shows that Data Eatta--tttttion over an order of magnitude slower than all other methods: its full-sequence likelihood evaluations per candidate question dominate the cost. Among the remaining methods, BED-LLM's runtime is comparable to to-and even slightly lower than than-Entropy and Split, despite computing the full EIG; this is because the additional conditional-entropy term in Eq. 3 reuses the same likelihood evaluations and adds negligible overhead. Prompt-Onl Only and CoT are the cheapest methods, as they require only single LLM generation call per turn with no hypothesis sampling or objective computation. Implicit Maximization falls in between: it samples hypotheses and candidate questions but replaces explicit EIG estimation with single LLM selection call. ICL Beliefs is slightly more expensive than BED-LLM because the absence filtering leads to lower-quality hypotheses, requiring much larger number of questions before the game terminates.
25

---

Published as a conference paper at ICLR 2026
GPT-44omiin
GPT-4o
Llama-3 1-8B
Liama-3 3.3-700
M Mistral-Large
Qwen2 5. 5-728
100
Success N Aninals
0
90
100
70
100
100
Success Success
0
0-
0-
60
80
70
80
on Things
20
20
20
Turn
Turn
Turn
Tum
Tur
Turn
Prompt-Only
Split
BED-LLM
Entropy
Beiefs
Impl.
Max.
Data-Est.
CoT
Figure 11: Success 20 Questions. Mean + standard error across 100 targets. BED-LLM beats all other methods across all datasets and models evaluated.
Q: GPT-4o-mini A: Qwen2.55726
Q: Qwen2.5-2 2-5-22
A: GPT-4o-mini
Sucues % on Animals
90
90
Sucuesa Sucuesa % on Things
on Celebrities
70
70
60
60
20
20
Turn
Turn
Prompt-Only
Split
BED-LLM
Entropy
ICL Beliefs
Impl. Max.
Data-Es: Est.
Figure 12: Full plots for 20 Questions Experiments with different questioner and answerer.
GPT-4o-mini
GPT-4o
1amma-33-70B
Mistral-Large
Qwen2.5-72B
4.5
Mean Rating
4.5
4.0
4.0
4.0
4.0
4.0
3.5
3.5
3.5
Turn
Turn
Turn
Turn
Tum
Prompt-Only
BED-LLM
Entropy
CoT
Figure 13: Mean rating across 10 film recommendations: mean + standard error across 200 users. BED-LLM beats all other methods across all datasets and models evaluated.
26

---

Published as a conference paper at ICLR 2026
Method
Runtime
Data fitt-Estimatio
1d 17h 13m 34s
ICL Beliefs
3h 10m 39s
Entropy
2h 46m 198
Split
2h 30m 358
BED-LLM
2h 28m 43s
Implicit Maximization
45m 10s
CoT
35m 28s
Prompt-Only
26m 29s
Table 3: Wall-clock runtimes for 20 Questions for Qwen2.5-72B on the entire Animals problem set.
F.3 EFFECT OF SEQUENTIALLY UPDATING THE BED-LLM LIKELIHOOD
As discussed in App. F.3, choose to static likelihood, (L [8, x2))), in the model factorization for BED-LLM. Alternatively, we could condition the likelihood on the full interaction history, i.e. PLLM 11 [he-1, 0, s++1])) However, this lead to undesirable effects (e.g. context- induced calibration shifts). We provide results in Tab. for the 20 Questions game where we update the likelihood, and demonstrate that leads consistently worse performance than BED-LLM, supporting our rationale in App. F.3 to keep the likelihood static.
Success Rate (%)
Dataset
Model
BED-LLM static likelihood
BED-LLM + likelihood updating
moi--4-mini
88 + 3,3
85 : 3.6
GPT-4o
93 2.6
86 + 3.5
Animals
Llama-3. 1-BBB
63 + 4.9
67 +: 4.7
Llama-3. 3.3-7-3.3-70B
79 = 4.1
80 = 4.0
Qwen2.5-72B
89
GPT-4o-mini
63 4.9
GPT-4o
86 3,5
83 = 3.8
Celebrities
Llama-3.1-8B
58 5.0
56 5.0
Llama-3.3 7.B
5.0
5.0
Qwen2.5-72B
3.7
4.6
GPT-4o-mini
49 5.0
43 5.0
GPT-4o
4.8
57 5.0
Things
Llama-3.
26 1 4.4
24 4 4.3
55 = 5.0
54 = 5.0
Qwen2.5-72B
4.9
4.9
Table 4: BED-LLM success rates across datasets and models. + numbers show the standard error of the mean estimated using vp(1 - p)/(n 1) where p is the success percentage and is the number of datapoints. This estimator is positively biased and thus conservative.
G FURTHER DESCRIPTION OF METHODS AND ABLATIONS
Prompt-Only: A direct prompting baseline where the model is asked immediately generate the next question given the dialogue history, no candidate generation, and no belief modeling (Fig. 14). This corresponds to the simplest and most common way users currently interact with LLM agents for question-asking tasks, and therefore serves as natural "standard [.LM prompting" baseline. After the L.MM has generated its question, waits for the user response and generates new question based on the new history.
27

---

Published as a conference paper at ICLR 2026
Figure 14: Prompt for the Prompt- Prompt-Onlyy method.
Your task to aak a serias quest ions to deduce idantity the 'person' if task =* "calebrities" else fanimal" if task =- 'animals' else fentity" that I'm thinking of with as Iew queries as possible,
Only ask questions that be answered 'yes', 'as' or 'maybe'. Da not ask for hint. Maka your question standalore with na Linebreaker.
Output format: <question>Your question hezets/queation>
Now atart asking question.
CoT: direct prompting baseline where the model is asked reason and provide action (Fig. 15) loosely following the ReAct framework (Yao et al., 2023b).
Figure 15: Prompt for the CoT method.
Your teak is sak series of questions deduce the identity of the 'person' If task "ce "calebritees alse "animal" if task == "animals ms else "encity' that T/m queries as possible.
thinking with Only aak quastions that can be answared by "yes', 'no" or 'maybe'. not ask for hints. The actual question you aak muat be standalone with no Linebreakers.
the following format for every response:
Thought: <briet reasoning about what to aak next>
Action: AšK["<a single yea/ne/maybe question with linebreaka>")
Now start by producing your rirat Thought and Action.
Split: Essentially version of method in which cast previous approaches, such Kobalczyk et al. (2025): uses the same candidate question generating method as BED-LLM, assumes a deter- ministic likelihood over hypotheses (i.e., each hypothesis deterministically predicts single answer to each question), and Evaluates the question on the sampled hypotheses, and selects the question that maximally balances the hypotheses, i.e. splits the current hypothesis into subsets whose sizes are close to equal possible.
Implicit Maximization (IM). The Implicit Maximization baseline a lightweight, reasoning-dree -riven method inspired by the of (ToT, Yao et al., 2023a) framework. ToT methods explicitly expand a search tree intermediate reasoning steps ("thoughts") before selecting an action. Implicit Maximization provides computationally efficient, collapsed variant of this idea:
Rather than explicitly branching over thoughts, the model is prompted to internally deliberate over several possible next questions and their consequences.
The branching and evaluation occur inside the model's chain-of-ther of-thouugtt, rather than through externally enumerated tree expansion.
The model then outputs the question it judges to most informative, performing an amortized, ToT-style lookahead within single LLM call.
Thus, IM captures the central intuition of Tree-of-Thoughts T over hypothetical fu- tures-whild avoiding the substantial computational cost of explicit search. serves as strong inference-time reasoning comparator to BED-LLM.
H EXPERIMENT DETAILS FOR 20 QUESTIONS
H. PROBLEM SETS
We evaluate across three distinct problem sets sets anis-lnimals, Celebrities, or Things with each con- taining mix of 100 obscure and common targets. Here, the problem set is just list of different 0* that will be individually provided to the answerer to instantiate different problems (e.g. we conduct a trial where 8* ="dog", then where 0* ="cat", etc). The list of targets is never provided to the questioner model to restrict the set of possible hypotheses: the questioner only prompted that is trying to identify "animal", "celebrity", or "thing". The problem sets
28

---

Published as a conference paper at ICLR 2026
Animals: set of animal species generated with OpenAl's o3 model ensure diverse mix and balanced taxonomy.
Celebrities: diverse set of public figures, as used by Zhang al. (2024).
Things: collection of everyday and exotic entities drawn from the web corpus, as used by Zhang et al. (2024); covers wide range of categories, from plants and clothing to professions, events, and mythical creatures.
To create the Animals problem set, we prompted OpenAl o3 (OpenAI, 2025, 03-2025-04-16) to generate a list of animals, using the prompt in Fig. 16. The resulting list is shown in Fig. 17. Alternatvve names (after character) were manually added.
Figure 16: Prompt for Animals problem set generation.
You are a zoclogist. Please generate List Living animal specles with very taxonomic diversity, including diversity in phyle, classes, orders, and families. Presen: each animel on different line.
African elephant
Sea otter
Kiwi
Bengal tiger
Coral snake
Leafeutter ant
Bald eagle
King cobra
Mantis shrimp
Blue whale
Harpy cagle
Ocelot
Red kangaroo
Lemur
Peregrine falcon
Giant panda
Koala
Quetzal
Snow leopard
Aye-aye Ayeaye
Raccoon
Green sea turtle
Snowy owl
Sand cat
American alligator
Elk
Tarantula
Bottlenose dolphin
Wolverine
Uakari
Emperor penguin
Caracal
Vicuña
Great white shark
Cassowary
Wildebeest
Golden poison frog Golden
Quokka
Rock hyrax dassie
poison dart frog
Pangolin
Yak
Honey bee
Saiga antelope
Zebra
Monarch butterfly
Galápagos tortoise Galapagos
Blue dragon nudibranch Blue
Okapi
tortoise
dragon sea slug
Chimpanzee
Sumatran orangutan
Chinchilla
Arctic fox
Red-eyed tree frog Redeyed tree frog
Dhole
Komodo dragon
Electric eel Flying fox
Giraffe
European badger
Cheetah
Moose
Gharial
Hammerhead shark
African grey parrot
Horseshoe erab
Axolot!
Scarlet macaw
Indigo bunting
Orca
Black mamba
Jerboa
Puffin
Albatross
Kakapo
Red panda
Humpback whale
Lionfish
Platypus
Dugong
Markhor
Rhinoceros beetle
Anaconda
Nautilus
Tasmanian devil
Kookaburra
Olive baboon
Wombat
Coyote
Pika
Sloth
Brown bear
Quoil
Blue-ringed octopus
|
Blue
Golden jackal
Rosy boa
ringed octopus
Capybara
Manatee
lbex
Narwhal
Japanese macaque
Figure 17: Animals problem set (generated using OpenAl o3, with manual curation)
29

---

Published as a conference paper at ICLR 2026
H.2 EVALUATION
We assess performance by tracking the questioner's ability to identify the hidden target 0* over the course of each game. At each turn we prompt it produce single guess for 0" via greedy decoding-thar is, we extract the highest likelihood candidate from the belief state of the questioner Pr(0; ht). This guess is evaluated against the true target 6* (including alternative names) using casc-insensitive exact string matching and we measure the proportion of correct guesses at each turn. Importantly, these evaluation guesses are not part of the questioner algorithm itself: they are extractions from the questioner's belief state P, (0; h2) and are excluded from h4-1 to not affect subsequent question selection. In line with the original rules of the game, we also introduce an explicit mechanism for the questioner to guess the answer part of its 20 questions: if the set of filtered hypotheses collapses to a single candidate, or a direct guess of 8" is evaluated as the maximally informative question by the acquisition function, the questioner asks "Is it (i emm This guess is evaluated using exact string matching, as above. If there is a match, the game terminates successfully; otherwise, if < 20, the game continues with the question and negative response included in h4-1 and counted towards the 20 question budget.
H.3 ALGORITHMIC DETAILS
Using our sample-then-fing process (see $3.1), we aim to sample at least N 15 hypotheses, repeating the eycle up to three times if needed (the exact number of hypotheses can be less than this as it may not be possible to generate sufficient valid hypotheses, especially in later experiment turns). The questioner generates .M 15 candidate questions to test, A using the "conditional generation" " approach of $3.2 when possible, but falling back on "unconditional generation" insufficient candidate hypotheses have been generated.
I EXPERIMENT DETAILS FOR PREFERENCE ELICITATION
1.1 PROBLEMS
To generate a set of ground-truth user profiles, we take a set of 200 real user ratings from the MovieL 100K dataset (Harper & Konstan, 2015), then use "oracle" LLM (namely, OpenAI's 03 model) to produce parugraph of text that is consistent with each distinct set of ratings, using the prompt Fig. 18. As was the case for the 20 Questions problems, this problem set never provided to the questioner and the set of allowed @ is not constrained.
Because we need the LLM to be able to meaningfully capture uncertainty in the space of responses, we restrict questions to be multiple-choice Specifically, the questioner is tasked with producing question along with five possible responses A/B/C/D/E. We then define each dt to be the question coupled with the possible responses, and each ye to be one of the letters A/B/C/D/E to provide restricted set of tokens over which we can measure entropy. Option E is further constrained to always be "none of the above" so that the answerer is not committed to choosing one of the directly generated choices if none are suitable.
1.2 EVALUATION
To again allow tracking of progress through the experiment, after each turn of the interaction f, the questioner generates ten film recommendations, conditioned on h,-1- These recommendations are checked for consistency with prior questions and answers; any are judged inconsistent then they are removed and additional recommendations are generated. The quality of the film recommendations is then assessed using an "LLM-as-judge" protocol (Zhu et al., 2025; Trivedi et al., 2024). Namely, the answerer evaluates each of the 10 films recommended by the questioner, conditioned the hidden target user profile 8*. It scores each film on a scale of 1 to 5 (in 0.5 increments), based on how well the recommendation aligns with 8* - this score is output together with brief justification to increase reliability. We report the mean rating and standard eтror across 200 users, over 5 question-ant answer turns.
30

---

Published as a conference paper at ICLR 2026
1.3 ALGORITHMIC DETAILS
For BED-LLM and Entropy, we compare M = 8 candidate questions at each turn and we aim to generate least N 5 candidate hypotheses. We the "unconstrained generation" approach of candidate question generation (see $3.2) as the user profiles can be quite diffuse and we are only generating small number of possible hypotheses that can be quite easy to split.
We note that data-estimation setup is not at all viable for this problem because the large number of tokens and varying dimensionality of each 0 sample mean that H(PLLM (0; [h F++1 1/+1l] only infeasible to estimate, but also is not meaningful measure of uncertainty.
Figure 18: Prompt used to generate ground-truti user profiles for preference elicitation task.
You will given grovided as a dieticnary structured by rating levels. Your
complete
rating history
Movietens dataset,
to thoroughly analyze user's preferences across their film ratings (from highest to lomest) Ther, write cohesiva, descriptive paragzaph (approximately 5-7 sentences) summarizing the user's overall film taste profile.
range
your response, explicitly
(inferred primarily from 4.5-5.0 ratings):
Highhiigtt the genzes, narrative styles, themes, tones, historical eres, and
emotionsl experiences that consistently resenate positively with this
avoid mentiening any specific film titles, characters, explicit plot points.
Neutrai Xixed Frelecences (inferred
ratings around 2.5-4.0):
if there indications of genze overlap conditional enjeyment,
such as certzin genres or styles they cccasionslly appreniate under specific
Dieliked Blemeats (inferred primarily from 0.5-1.5 ratingsl:
clearly outline the genres, narrative characteristica, tones, or emotional impacts that the user consistently finds unappealing or poorly executed.
Your peragraph must precise, informetive, nuanced, capturing the complexity and specificity of the user'a movie preferences. The sesulting profile should be cleaz and detailed enough foz recommendal system. sccurately predict the user'a likely enjoyment dislike of other films based their established patterns of taste.
balanced, affestively
Prozeed carefully, reasoning explicisly about the user's averall rating patteras rather than "slying exe exa vsivaly extre ratings, to form comprehensiva, stable, representative film greference profile.
J
CODE AVAILABILITY
Code is available at https: htt.:ppp//gtthh...ccm///errrrrhr
31


Reviews:
[{"review_id": "B2IuxY66HI", "reviewer": "Reviewer_Jn86", "summary": "This paper presents BED‑LLM. It treats multi‑turn question asking as sequential Bayesian experimental design. At each step, the model makes several candidate multiple‑choice questions. It then picks the one with the highest expected information gain (EIG) and asks it. After the answer, it updates a simple belief over possible hypotheses by sampling, filtering for consistency and renormalizing. The method uses a prior–likelihood setup and a low‑variance EIG estimator based on the model’s logits. It avoids the common mistake of using only predictive entropy. The authors show gains on 20 Questions and movie‑preference tasks, including when the questioner and answerer are different models.", "questions": "- Why threshold 0.2, and why uniform reweighting? How sensitive are results to these, and what happens with temperature scaling?\n- For free‑text or continuous y, what EIG approximations or discretizations are viable?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Clear problem formalization and principled objective. The paper cleanly frames multi‑turn question selection as sequential Bayesian experimental design (BED) and optimizes incremental expected information gain (EIG) in a concrete loop: generate candidate questions -> estimate EIG  -> select the best question -> update the belief state. \n- Rigorous treatment of uncertainty (beyond predictive entropy). The authors explicitly show that predictive entropy ≠ EIG and that dropping the expected likelihood entropy term selects ambiguous or irrelevant questions. They provide an intuitive example and ablations (“Entropy” baseline) demonstrating real performance gaps. \n- Sensible modeling choice. It uses a prior–likelihood factorization that puts uncertainty in the answer space y (small and enumerable) rather than the often much bigger hypothesis space $\\theta$. Practically, questions are written as multiple‑choice so probabilities and entropies are reliable.\n- Belief update that fixes in‑context issues. Instead of relying on raw in‑context updates (which can be inconsistent and overconfident), it samples hypotheses, filters them against the history, retains consistent ones across turns, and reweights uniformly. Removing this step hurts performance in ablations, which shows it matters.", "weaknesses": "- No compute time accounting. Each turn can be heavy: sample at least N=15 hypotheses (with up to three generate‑and‑filter rounds), score M=15 candidate questions, etc. The paper doesn’t report tokens, wall‑clock, or cost curves to show the overhead vs. baselines.\n- Sensitive to API log‑probabilities. The EIG estimator and the filtering step assume access to stable token‑level probabilities. Some APIs limit this. \n- The algorithm optimizes the next question’s EIG only. The paper itself notes that sequential BED can be suboptimal and points to policy‑based alternatives, but it doesn’t compare against them here.\n- Depends on multiple‑choice answers. The method works by keeping the answer space small and enumerable, so it doesn’t directly handle open‑ended text or continuous answers. This is by design to make probabilities and entropies reliable, but it narrows where the approach applies.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eg7Lb3wj1Z", "reviewer": "Reviewer_T2zx", "summary": "This paper presents BED-LLM, a framework that integrates BED principles into LLMs to enable adaptive and information-efficient query generation. The core idea is to model belief over hypotheses and select the next query by maximizing an approximate EIG, implemented through an LLM-mediated sampling and likelihood estimation process. The formulation adapts Bayesian inference perspectives into a framework for LLM-driven reasoning. The experiments, however, are limited to small, synthetic tasks and do not provide sufficient evidence that the proposed method yields general improvements in interactive reasoning or adaptive planning. The contribution is conceptually promising and well-articulated, but the empirical validation is too narrow to establish practical impact.", "questions": "See above weaknesses.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Presents a clear and well-motivated connection between Bayesian experimental design and LLM-based information gathering.\n- Offers a unified probabilistic framing that clarifies the relationship between prompting, belief updates, and adaptive query selection.\n- Demonstrates measurable gains over naïve baselines on synthetic tasks, suggesting that EIG-guided prompting can improve efficiency in principle.", "weaknesses": "- Limited scope of evaluation. Although the paper is positioned as a general framework for intelligent and adaptive information gathering with LLMs, the experiments are confined to small, toy-scale domains (20-Questions and synthetic movie recommendation). These tasks are useful for illustration but are quite far from the complex, noisy, multi-step reasoning settings the paper emphasizes introduction emphasizes. As a result, the evaluation does not convincingly demonstrate that BED-LLM generalizes beyond simple controlled environments.\n- Missing planning and reasoning baselines. The paper compares primarily against naïve or ablated versions of its own approach, omitting stronger baselines such as reinforcement learning, Monte Carlo tree search, or other uncertainty-driven planning methods that have been explored for adaptive query generation in LLMs. Without these comparisons, it is difficult to attribute observed gains to the proposed Bayesian-experimental-design formulation rather than to prompt structure or candidate filtering.\n- Lack of validation for expected information gain (EIG) approximations. The core methodological claim is that BED-LLM uses approximations of expected information gain to guide question selection. However, there is no empirical or analytical evaluation of the accuracy or stability of these approximations. The paper reports only downstream success metrics, leaving unclear whether the observed performance improvements arise from better EIG estimation or unrelated modeling choices. A more direct analysis, for e.g., comparing true vs. approximated EIG, or assessing consistency under varying priors, would greatly strengthen the argument.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ssrhW3WoLH", "reviewer": "Reviewer_Ah5k", "summary": "The authors propose BED-LLM, a method designed to improve the information gathering ability of large language models (LLMs). The main idea of the paper is to select questions that maximize the expected information gain (EIG), enabling the model to acquire relevant information more efficiently than existing approaches. The method requires no parameter updates or fine-tuning and can be easily used with any pretrained LLMs. Through experiments on the 20 Questions game and film preference elicitation tasks, the authors demonstrate that maximizing EIG significantly enhances an LLM’s ability to ask informative and discriminative questions. These results indicate that EIG is an effective metric for improving information gathering in LLMs.", "questions": "The BED-LLM approach appears to be computationally heavy, as it generates multiple candidate questions, estimates their expected information gain (EIG), and updates a belief distribution at each turn. It would be helpful to understand how the computational cost compares to baseline methods, such as Naive or Split, in terms of inference-time overhead.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "-\tBED-LLM goes beyond simply identifying questions that elicit new information. It also evaluates whether each question is contextually coherent and whether it contributes to determining the final answer. By incorporating these considerations, the method effectively avoids asking irrelevant or redundant questions, guiding the model toward more meaningful and goal-oriented information gathering.\n\n-\tThe method is model-agnostic. It can be used with any existing LLMs without any parameter updating or fine-tuning, which greatly enhances its practicality and generalizability.\n\n-\tThe authors decompose BED-LLM into four distinct components (Entropy, Data-Estimation, ICL Beliefs, Implicit Maximization)  and perform ablation experiments to isolate the contribution of each method. This experimental design enables a quantitative assessment of how each component contributes to the model’s information-gathering performance, offering empirical evidence of the method’s internal effectiveness.", "weaknesses": "-\tThe experimental evaluation is relatively limited in scope. The 20 Questions setting, while well-structured, represents a simplified and highly constrained environment that may not adequately capture the ambiguity and uncertainty inherent in real-world information-gathering tasks. Moreover, the chosen topics—animals, celebrities, and things—are narrow in domain and may not generalize well to more complex or abstract scenarios. This raises questions about the method’s robustness and applicability across diverse contexts.\n\n-\tThe paper does not clearly define the termination criterion for the questioning process. In the 20 Questions experiment, the interaction terminates either when the model exhausts all twenty turns or when only a single hypothesis remains and the model correctly identifies it.\nIn contrast, in the film preference elicitation setup, the model proposes a list of films at each turn, which is then evaluated against the user’s preferences, but the stopping condition for this process is not clearly specified. As a result, it remains unclear how and when BED-LLM determines that sufficient information has been gathered to conclude the interaction.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cyfQeAjGQp", "reviewer": "Reviewer_4sXe", "summary": "The paper introduces a Bayesian Experimental Design (BED) inspired algorithm that enables LLMs to ask informed questions to a user or an external source. The approach leverages the internal belief probabilities of the LLM to estimate the prior and conditional distributions over queries and answers, allowing it to select optimal questions based on Expected Information Gain (EIG). EIG is computed as the difference in entropy between the posterior and prior beliefs, capturing the expected reduction in uncertainty after conditioning on the queried question and its potential answers.The algorithm proposes several strategies to construct and update the belief distributions through prompting and sampling from the underlying LLM. Notably, it uses an external LLM to generate potential questions candidates rather than a fixed set of known questions. Experiments on both the “20 Questions” and a preference elicitation benchmark show modest improvements compared to “Naive” and “Split” baselines.", "questions": "1. The paper uses $p_{\\text{LLM}}(y; \\theta, x)$ as an approximation of $p(y \\mid \\theta, x)$. Is there evidence demonstrating that this approximation is sound? Specifically, have you provided empirical validation from your own experiments or cited related work that supports this substitution? A clearer justification seems necessary, given that this approximation is central to the computation of the joint probability $p(y, \\theta, x)$.\n\n2. In line 159, you state that \"autoregressive sequential rollouts often lead to more nuanced and diverse behavior than repeated static likelihood queries.'' Could you elaborate on why having ``more nuanced and diverse behavior'' is important in a BED framework? What advantage does this bring in relation to your work?\n\n3.  In Appendix~A.1, you mention that \"we choose not to update the likelihood model as more data is gathered,'' meaning $h_{t-1}$ is not used to update the likelihood. The justification provided---\"for many problems, our beliefs on $\\theta$ capture all the required information to predict $y|x$''---seems inconsistent with your prior, which does depend on $h_{t-1}$. Wouldn’t it therefore be more accurate to include $h_{t-1}$ in your experiments rather than exclude it? I’m not fully convinced by the argument that doing so is \"not necessary.''\n\n4.  The paper claims that one advantage of the proposed method is that, unlike prior work, it is not restricted by pre-specifying allowable entities: \"In general, these previous works have also required restrictions on the space of allowable hypotheses $\\theta$, whereas we do not tell the LLM this set of target entities, so the space of $\\theta$ is bounded only by what the LLM can generate.'' However, your approach still requires $\\theta$ when computing the EIG. Is the key difference that prior work assumes $\\theta$ is explicitly given, while your approach allows $\\theta$ to be generated by the LLM? \n\n5. Could you provide details on how the \"Naive'' and \"Split'' baselines are implemented? The current manuscript lacks sufficient description of their setup. Additionally, how does the number of possible answers (20 vs. 500) affect performance? Does it influence your results?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The paper addresses an important challenge in information seeking for LLM, aiming to formalize how LLMs can ask meaningful and informative questions.\n2. The proposed framework, based on Bayesian Experimental Design (BED) and Expected Information Gain (EIG), is theoretically well-motivated and offers strong interpretability and soundness for modeling information-seeking behavior.\n3. The authors provide detailed explanations of their assumptions and offer clear justifications for these assumptions", "weaknesses": "The paper would benefit from improvements in clarity and presentation, which would enhance its accessibility to readers. \n\n1. The overall structure of the paper is not well organized and is difficult to follow. The methodology section is dense and provides minimal examples to clarify key ideas. The authors should consider adding illustrative visuals or concrete examples to make the approach more understandable. \n\nSome claims and assumptions are insufficiently motivated/addressed, and the arguments supporting them appear insufficient or not well justified. The author should refrain from making claims and general conclusion without strong supporting evidence. \n\n2. Several claims in the paper are not sufficiently supported by experiments or reasoning. For instance, the authors state that the ``approach often fails to appropriately incorporate the information from $h_{t-1}$, leading to a belief distribution inconsistent with past observations,'' yet no examples, analyses, or ablations are provided to substantiate this claim. \n3. Some simplified assumptions are concerning. In particular, replacing $p(y \\mid \\theta, x)$ with $p_{\\text{LLM}}(y; \\theta, x)$ when constructing the joint distribution $p(y, \\theta; x)$ raises concerns about correctness and validity. In appendix A.1 the author's justification for not updating likelihood $p_{\\text{LLM}}(y; [\\theta, x_t])$  is \"$\\theta$ capture all the required information to predict y|x\" which also lacks evidence to support the claim.  \n\nThe paper lacks sufficient specification of experimental details and design choices, and provides limited baseline comparisons or ablation analyses. The two baselines included in the paper are not representative of existing approaches, offering little context for interpreting the reported results. Moreover, since the proposed method requires multiple LLM calls to generate candidate hypotheses and questions, reporting computational costs such as token usage or inference time would be essential to contextualize performance. Finally, the lack of detailed descriptions or illustrative examples for the baselines is concerning make it difficult to assess the fairness of the comparisons.\n\n4. The paper does not discuss computational costs such as token usage, inference time, or scalability. Including such details would provide important context for assessing the practicality of this approach beyond toy problems.\n5. Prompt based methods such as Reflexion, ReAct, and CoT should have been included for a more meaningful evaluation. \n6. The experimental setup is not clearly explained. For example, the paper does not define what the `\"Naive'' baseline represents, and the \"Split'' baseline is only vaguely described. The comparison to standard LLM prompting methods is also limited---For the preference elicitation task, including only the ``Naive'' baseline is insufficient.\n7. The paper lacks ablation studies analyzing the impact of different design choices. Without these analyses, it is difficult to determine which components of the proposed approach actually contribute to the reported performance improvements.\n\nI think the paper is well motivated and the core idea is well-justified. The paper itself requires substantial improvement in clarity, organization, and experimental rigor. The presentation is difficult to follow, several design choices and assumptions are not well motivated, and key claims lack sufficient empirical support or ablation analysis.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)