PaperlayerView exact revision on arXiv

Source-linked AI summary

BED-LLM: Intelligent Information Gathering with LLMs and Bayesian Experimental Design

Deepro Choudhury, Sinead Williamson, Adam Goliński, Ning Miao, Freddie Bickford Smith, Michael Kirchhof, Yizhe Zhang, Tom Rainforth

arXiv:2508.21184v3cs.CLcs.AIstat.ML

TL;DR

LLMs often struggle to adapt questions to responses already gathered, limiting interactive information gathering. BED-LLM uses sequential Bayesian experimental design to select queries by expected information gain and update beliefs; it reports broad gains, including a 37.4-percentage-point average improvement over direct prompting in 20 Questions. Its belief construction must address limitations in LLM priors and in-context updates.

  • Problem

    LLMs can generate coherent questions but often fail to adapt them to previously gathered responses, despite the need for targeted information gathering in interactive tasks.

    Source: §1 · p. 1

  • Method

    BED-LLM iteratively selects queries by expected information gain using an LLM-derived probabilistic model, then updates beliefs from received responses.

    Source: §1 · pp. 1–2

  • Results

    BED-LLM improves 20 Questions success rates by an average of 37.4 percentage points over direct prompting, with gains across tested LLMs and target quantities and noticeable improvements in movie recommendations.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The results indicate that explicit EIG-based adaptive query selection can improve interactive information gathering compared with direct prompting and simpler sequential BED approximations.

    Source: §1 · p. 2

    LLM in-context belief updates can fail to incorporate history faithfully, sampling hypotheses incompatible with past observations and becoming prematurely overconfident, especially as history grows.

    Source: §3.1 · p. 4

Abstract

from arXiv · show

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.

1 INTRODUCTION

LLMs can generate coherent questions but often fail to adapt them to earlier responses, limiting interactive information gathering. BED-LLM selects queries by expected information gain and updates beliefs from responses; it improves results across 20 Questions and movie recommendations.

1 INTRODUCTION

  • LLMs often produce coherent questions in single-turn settings but struggle to tailor questions to responses already gathered during interactive tasks.The paper identifies shortcomings across guessing games, task clarification, IT task automation, and multi-step tool use.Source: §1 · p. 1
  • BED-LLM frames interactive information gathering as sequential Bayesian experimental design, selecting queries to maximize expected information gain and updating beliefs from responses.The process iterates between choosing queries and updating beliefs about a variable of interest.Source: §1 · pp. 1–2
  • BED-LLM’s performance depends on model formulation, belief updating, and EIG estimation, including using answer-space uncertainty rather than uncertainty over the underlying hypotheses.The model should not rely solely on in-context learning to update beliefs.Source: §1 · p. 2
  • BED-LLM improves 20 Questions success rates by an average of 37.4 percentage points over direct prompting, with gains across LLMs and target quantities and no decreases across tested setups.Success rates more than doubled in over half of the setups considered; the paper also reports noticeable improvements for movie recommendations.Source: §1 · p. 2

2 PROBLEM FORMULATION AND BACKGROUND

The section formalizes information gathering as sequential queries about a target quantity, with beliefs updated from interaction history. It motivates in-context updating, introduces the joint model underlying Bayesian experimental design, and explains how expected information gain supports adaptive query selection.

2 PROBLEM FORMULATION AND BACKGROUND

  • The paper focuses on deployment-time changes rather than finetuning because information-gathering tasks rarely provide task-specific data upfront, while model-level improvements could complement this approach.Deployment-time methods avoid finetuning’s cost and difficulty and apply to existing LLMs.Source: §2 · p. 2
  • Information gathering begins with a target quantity θ and prior p(θ), then uses queries and responses to refine beliefs based on the collected history.The belief distribution p(θ; h_{t−1}) provides a foundation for information-theoretic query selection, even when it is not explicitly defined.Source: §2 · p. 2
  • Although the exposition focuses on explicit questions to users, the approach also applies to retrieving documents or calling external functions.Source: §2 · p. 2

2.1 IN-CONTEXT UPDATING OF BELIEFS

  • In-context updating incorporates interaction history by including prior question–response pairs in the prompt, but may produce beliefs inconsistent with past observations.The paper notes that contextual information may not be treated equally; its belief dependency on history is not necessarily derived through explicit probabilistic conditioning.Source: §2.1 · p. 2

2.2 INFORMATION-THEORETIC EXPERIMENTAL DESIGN

  • Bayesian experimental design uses a joint generative model p(θ, y; x) for the target quantity, response, and design, and selects designs to maximize expected utility under that model.Source: §2.2 · p. 3
  • Expected information gain in θ can be viewed as mutual information between θ and y or as the expected reduction in entropy over θ after observing model-generated data.The section also describes an equivalent expected entropy reduction over data after simulating θ from the prior.Source: §2.2 · p. 3
  • In sequential design, new history updates the joint model and therefore the incremental EIG objective for the next query.The update conventionally comes from Bayesian updating, but non-Bayesian updates are also used in some settings.Source: §2.2 · p. 3

3 SEQUENTIAL BAYESIAN EXPERIMENTAL DESIGN WITH LLMS

The section formulates adaptive LLM querying as sequential Bayesian experimental design, with query choice guided by expected information gain and beliefs updated from responses. It highlights that model construction, belief updating, candidate generation, and EIG estimation all affect the approach.

3 SEQUENTIAL BAYESIAN EXPERIMENTAL DESIGN WITH LLMS

  • BED-LLM pairs a prior over θ with the LLM likelihood of responses given θ and a query, while alternative joint constructions can yield different distributions.The preferred pairing can depend on the relative complexity of the hypothesis and response spaces.Source: §3 · p. 3
  • At each turn, BED-LLM generates candidate questions, estimates each question’s EIG, asks the highest-scoring question, and updates the interaction history with the response.The procedure repeats using the expanded history.Source: §3 · p. 4

3.1 PRIOR CONSTRUCTION AND BELIEF UPDATING

  • Full Bayesian updates can require prohibitively many LLM evaluations, while direct in-context beliefs can be overconfident or inconsistent with past observations.The cited concerns include overconfidence in a small set of hypotheses and failures to incorporate history faithfully.Source: §3.1 · p. 4
  • BED-LLM filters sampled hypotheses for compatibility with the history, retains consistent prior-turn hypotheses, and promotes diversity through batched generation and a uniform distribution.Compatibility is assessed using the likelihoods of observed answers, with rejection based on a predefined threshold.Source: §3.1 · p. 4

3.2 GENERATING CANDIDATE QUESTIONS

  • Because direct optimization over all questions is infeasible, the method samples diverse candidates, either from the history alone or conditioned on hypotheses to encourage balanced partitions.Conditional generation is effective for discrete spaces but less so for complex, overlapping hypotheses; questions use multiple-choice format.Source: §3.2 · p. 5

3.3 ESTIMATING EIG FOR EACH QUESTION

  • The Rao–Blackwellized EIG estimator uses samples from the filtered belief distribution and the LLM’s predictive probabilities for candidate-question responses.When possible, the conditional response probabilities are computed from the LLM’s logits.Source: §3.3 · pp. 5–6
  • An entropy-only score can favor noisy questions: high response uncertainty is informative only when expected response uncertainty given θ is low.The EIG discounts uncertainty that remains even when the target is known, unlike methods assuming deterministic responses.Source: §3.3 · p. 6

4 ON THE SPECIFICATION OF p(θ, yt; ht−1, xt), AND ITS IMPLICATIONS

The section compares prior–likelihood and data–estimation pairings, arguing that the choice depends on model flexibility, conditional-distribution reliability, and the complexity of the target and response spaces.

4 ON THE SPECIFICATION OF p(θ, yt; ht−1, xt), AND ITS IMPLICATIONS

  • Prior–likelihood gives direct control over the prior on θ, whereas data–estimation can flexibly specify simulated responses, for example using an external data simulator..Source: §4 · p. 6
  • Choose the pairing according to which conditional distribution’s uncertainty is more trustworthy and easier to estimate; generally favor prior–likelihood when θ is more complex and data–estimation when y is more complex.For the problems considered, y is less complex than θ, favoring prior–likelihood.Source: §4 · p. 7
  • Prior–likelihood exposes the belief state directly, while data–estimation requires integrating over synthetic responses and generally makes beliefs depend on the next question.Conditional distributions also require explicit or cheaply estimated probabilities, making them harder to specify for large spaces.Source: §4 · pp. 6–7

5 RELATED WORK

Related work has explored LLM-generated information-seeking questions and uncertainty-based query selection, but the cited approaches differ from BED-LLM in their model formulation and assumptions.

5 RELATED WORK

  • Prior work showed some adaptive information-seeking ability in LLMs, but reported that such questions can fail to extract important information.Source: §5 · p. 7
  • The cited uncertainty-based query methods do not provide BED-LLM’s joint-model analysis, assume deterministic likelihoods, and often restrict hypothesis spaces or require further assumptions or approximations.Source: §5 · p. 7

6 EXPERIMENTS

The experiments test BED-LLM in 20 Questions and film-preference elicitation, finding gains over prompting and alternative adaptive strategies. They also examine how model formulation and belief updating affect 20 Questions performance.

6 EXPERIMENTS

  • The experiments compare information-gathering methods in 20 Questions and preference elicitation, using Prompt-Only, chain-of-thought prompting, and Split as 20 Questions baselines.In preference elicitation, Split is not used because its deterministic-likelihood assumption is considered unreasonable.Source: §6 · pp. 7–8, §6.2 · p. 10

6.1 20 QUESTIONS

  • BED-LLM significantly outperforms Prompt-Only and Split across all tested 20 Questions problems and LLMs.Its final success rate is typically more than double Prompt-Only’s.Source: §6.1 · p. 8, Figure 2 · p. 8, Table 1 · p. 9
  • BED-LLM outperforms all alternatives in 20 Questions; Entropy is the strongest alternative, while Implicit Maximization improves on Prompt-Only.Entropy performs only slightly better than Split, and Implicit Maximization is described as cheap to run.Source: §6.1 · p. 9
  • BED-LLM’s prior–likelihood approach substantially outperforms Data–Estimation, which still beats Prompt-Only but performs worse than Entropy.The authors identify estimating uncertainty in response space rather than hypothesis space as important in this comparison.Source: §6.1 · p. 9
  • Simple in-context belief updating causes massive performance drops, and prompting an LLM to select among candidate questions works much less well than explicit EIG estimation.The latter approach uses BED-LLM’s candidate-question and hypothesis sampling routines but replaces explicit EIG estimation with LLM judgment.Source: §6.1 · pp. 9–10
  • BED-LLM’s benefit persists when the questioner and answerer differ, a model-misspecification setting the authors identify as relevant to real-world users.Figure 2 reports success rate across 100 targets per dataset.Source: Figure 2 · p. 8, §6.1 · p. 10

6.2 PREFERENCE ELICITATION

  • In preference elicitation, BED-LLM produces higher-rated film recommendations than Prompt-Only and Entropy, with the clearest benefit when questioner and answerer belong to different model classes.The evaluation uses user profiles as targets and assesses ratings across ten recommendations for each of 200 users.Source: §6.2 · p. 10, Figure 3 · p. 10

7 CONCLUSION

The conclusion presents BED-LLM as a principled sequential Bayesian experimental-design approach to interactive information gathering, with substantial performance improvements. The appendices explain its modeling and updating choices, their conditions, and how they differ from related approaches.

7 CONCLUSION

  • BED-LLM’s justified choices in joint-model factorization, belief updating, and EIG estimation yield substantial performance improvements for interactive, multi-turn information gathering.The authors conclude that principled EIG-driven strategies can produce substantial gains in this setting.Source: §7 · p. 10

A.1 UPDATING THE LIKELIHOOD

  • For many problems, a static likelihood pLLM(yt; [θ, xt]) avoids unnecessary history context when beliefs about θ already capture the information needed to predict y given x.Use a history-conditioned likelihood instead when θ does not capture all information from previous data.Source: §A.1 · p. 17

A.2.1 PREDICTIVE ENTROPY IS NOT A GOOD APPROXIMATION OF EIG

  • High predictive entropy can have zero EIG when an answer, such as ice-cream preference, says nothing about film preferences; different posterior updates make another uncertain answer informative.The experiments also find that the Split baseline and Entropy ablation degrade significantly relative to full EIG, without saving LLM evaluations.Source: §A.2.1 · p. 17, Figure 4 · p. 17

A.2.2 EIG ESTIMATOR

  • Replacing the sampled-response estimate with the LLM’s direct history-conditioned response distribution would no longer estimate true EIG because the likelihood and marginal data distribution would be inconsistent.The authors report that sampling θ and then y tends to yield better response uncertainty than sampling y directly, and the substitution offers no meaningful computational benefit.Source: §A.2.2 · p. 18

A.3 PRIOR CONSTRUCTION AND BELIEF UPDATING

  • In-context updating can miss distinct historical evidence and struggle to infer user-specific θ, which often cannot be predicted from data beyond the user’s responses.The authors suggest these are reasons in-context learning may struggle in information-gathering settings.Source: §A.3 · p. 18

B.1 AN ALTERNATIVE VIEW ON THE FAITHFULNESS OF CONDITIONAL DISTRIBUTIONS / B.2 CHOICE OF θ

  • The preferable model pairing depends on which conditional’s entropy is meaningful: prior–likelihood suits constrained y and complex θ, while data–estimation suits constrained θ and free-form y.When formulating θ, choose a representation whose entropy measures meaningful uncertainty; code outputs may be more informative than raw code because multiple programs can perform the same operation.Source: §B.1 · p. 18, §B.2 · pp. 18–19

B.3 ALIGNMENT BETWEEN EIG AND BELIEF UPDATING PROCEDURE

  • The EIG pairing should reflect the practical update: prior–likelihood aligns with Bayesian updates, while data–estimation aligns with in-context updates; directly targeting final-horizon uncertainty is typically computationally infeasible.The authors describe the BED-LLM update as between in-context and Bayesian updating, depending on the problem and on which uncertainty the LLM captures more faithfully.Source: §B.3 · pp. 19–20

C EXTENDED RELATED WORK

  • Related approaches include deterministic-likelihood query selection, meta-trained data–estimation, conformal-set surrogates, and post-training; BED-LLM does not address fine-tuning and may complement policy-based BED.The cited conformal-set approach requires calibration data and is limited to closed-world settings with finite labels and predefined queries.Source: C EXTENDED RELATED WORK · pp. 20–21

D DATA–ESTIMATION METHOD

The Data–Estimation method models responses and hypotheses jointly through a data–estimation pairing. Its EIG calculation combines expected posterior entropy with a design-dependent marginal entropy over hypotheses.

D DATA–ESTIMATION METHOD

  • The Data–Estimation method uses the response distribution given history and design, multiplied by the hypothesis distribution given history, design, and response, as its joint model.This is the data–estimation pairing used by the method.Source: D DATA–ESTIMATION METHOD · p. 21

D.1 EIG ESTIMATION

  • Its EIG is marginal entropy over θ minus expected posterior entropy, with the marginal on θ formed by integrating over responses.Because the resulting mixture’s components and weights depend on the candidate question, its marginal entropy varies across designs and cannot be omitted.Source: §D.1 · pp. 21–22
  • For finite enumerable answer spaces with closed-form response probabilities, both EIG terms can be computed directly; posterior entropies can use LLM logits or sampling.The marginal entropy remains an estimated mixture entropy, using sampled hypotheses and a plug-in or nearest-neighbor estimator, or response enumeration.Source: §D.1 · p. 22
  • When responses cannot be enumerated, both EIG terms require Monte Carlo estimation, while the mixture-entropy computation can cost O(M × N) autoregressive probability evaluations.The cost arises from evaluating sampled hypotheses across mixture components over full hypothesis texts.Source: §D.1 · p. 22

D.2 IMPLEMENTATION

The implementation estimates data–estimation EIG by sampling hypotheses from a response-weighted mixture and evaluating their probabilities across answers. Candidate construction addresses concentrated LLM beliefs through diverse joint generation, history-based filtering, and a uniform prior.

D.2 IMPLEMENTATION

  • In the experiments, enumerable answers allow direct computation of expected posterior entropy, while marginal entropy is estimated from mixture-sampled θ values by enumerating answers.This requires M × |Y| evaluations per candidate question, each involving a forward pass over the hypothesis text.Source: §D.2 · p. 22

D.3 GENERATING CANDIDATE HYPOTHESES

  • The raw LLM hypothesis distribution can concentrate on a few answers, making it less diverse than valid ground-truth hypotheses and harming Data–Estimation performance.The diagnostic example uses 200 independent samples; the aggregated view is diagnostic, while Algorithm 1 uses probabilities of individual samples.Source: §D.3 · p. 22, Figure 5 · p. 23

E GENERATING CANDIDATE HYPOTHESES FOR BED-LLM

  • Candidates are generated jointly in one LLM rollout and treated as a uniform set because the raw hypothesis distribution is overconfident.The authors describe joint generation as sampling from an autoregressive list distribution.Source: E GENERATING CANDIDATE HYPOTHESES FOR… · p. 24
  • A diversity-oriented prompt varies semantic features, prioritizes the newest history exchanges, and uses temperature 1.3 for 20 Questions versus 1 for preference elicitation.The earlier question–answer pairs remain in context while the most recent pair is placed first.Source: E GENERATING CANDIDATE HYPOTHESES FOR… · p. 24
  • Candidates are filtered when the LLM assigns the previous answers a probability below 0.2, and compatible candidates from earlier rounds are retained.Generation and filtering are repeated twice, or three times if too few hypotheses have been generated.Source: E GENERATING CANDIDATE HYPOTHESES FOR… · p. 24
  • The method uses a uniform prior over generated hypotheses rather than reweighting them by the LLM’s internal probabilities.Importance sampling is possible in principle but is not used in practice.Source: E GENERATING CANDIDATE HYPOTHESES FOR… · p. 24
  • Diversity strategies vary across LLMs, but the experiments keep their parameters constant across models for fairness.Source: E GENERATING CANDIDATE HYPOTHESES FOR… · p. 24

F ADDITIONAL EXPERIMENTAL RESULTS

BED-LLM remains the best-performing method across the extended 20 Questions evaluation, while additional analyses examine EIG-estimator convergence, runtime, recommendation ratings, and likelihood updating.

F.1 20 QUESTIONS AND PREFERENCE ELICITATION

  • BED-LLM remains best at every turn through 50 turns and beats all other methods across evaluated datasets and models.The performance gap narrows later as tasks saturate, but BED-LLM retains its advantage.Source: Figure 9 · p. 25, Figure 11 · p. 26
  • At |Θ| = 10, the five candidate questions’ EIG ranking already matches the ranking at |Θ| = 85, supporting a moderate hypothesis-sample budget.The estimates converge rapidly, and question selection depends on the ranking rather than the absolute EIG values.Source: §F.1 · p. 25, Figure 10 · p. 25

F.2 WALL-CLOCK TIMES

  • BED-LLM’s runtime is comparable to—and slightly lower than—Entropy and Split despite computing full EIG.Table 3 reports wall-clock runtimes for Qwen2.5-72B across the full Animals problem set; the conditional-entropy term reuses likelihood evaluations and adds negligible overhead.Source: §F.2 · p. 25, Table 3 · p. 27
  • BED-LLM beats all other methods across evaluated datasets and models on mean ratings for 10 film recommendations.Figure 13 reports mean ± standard error across 200 users.Source: Figure 13 · p. 26

F.3 EFFECT OF SEQUENTIALLY UPDATING THE BED-LLM LIKELIHOOD

  • Conditioning the likelihood on the full interaction history consistently worsens 20 Questions performance relative to BED-LLM’s static likelihood.Table 4 reports BED-LLM success rates across datasets and models; its ± values are standard errors estimated with a positively biased, conservative estimator.Source: §F.3 · p. 27, Table 4 · p. 27

G FURTHER DESCRIPTION OF METHODS AND ABLATIONS

The appendix describes prompting, deterministic-split, and reasoning-driven comparison methods, alongside the construction of the 20 Questions problem sets.

G FURTHER DESCRIPTION OF METHODS AND ABLATIONS

H.1 PROBLEM SETS

  • The three 20 Questions sets—Animals, Celebrities, and Things—contain diverse targets, and the target lists are not given to the questioner.Celebrities and Things draw on sets used by Zhang et al. (2024); Things span categories including plants, clothing, professions, events, and mythical creatures.Source: §H.1 · pp. 28–29
  • The Animals set was generated with OpenAI o3 and manually curated with alternative names added.The generation prompt and resulting list are shown in Figures 16 and 17; the model is identified as OpenAI o3 (OpenAI, 2025, o3-2025-04-16).Source: §H.1 · p. 29, Figure 16 · p. 29, Figure 17 · p. 29

H.2 EVALUATION

The 20 Questions evaluation tracks the questioner’s belief-based guesses and success over turns, with defined hypothesis and candidate-question budgets; preference profiles are also constructed from user ratings.

H.2 EVALUATION

  • Performance is measured by the proportion of correct greedy guesses from the questioner’s belief state at each turn, using case-insensitive exact matching.Evaluation guesses are excluded from the interaction history; games allow explicit guesses within the 20-question budget and terminate on a match.Source: §H.2 · p. 30

H.3 ALGORITHMIC DETAILS

  • For 20 Questions, the questioner aims to sample at least 15 hypotheses and generates 15 candidate questions, with up to three sampling cycles.Conditional question generation is used when possible, with unconditional generation as fallback; valid hypothesis counts can be lower than 15, especially later in a game.Source: §H.3 · p. 30

I.1 PROBLEMS

  • Ground-truth preference profiles are generated from 200 MovieLens-100K user-rating sets by an oracle LLM, and the questioner is not given the profile set or a constrained target space.Source: §I.1 · p. 30
  • Preference questions are multiple-choice with five responses A/B/C/D/E, where E is always “none of the above,” enabling uncertainty measurement over a restricted response set.Source: §I.1 · p. 30

I.2 EVALUATION

The preference task evaluates recommendation quality through user-profile-conditioned ratings, with specified candidate budgets and a limitation on data–estimation for this setting.

I.2 EVALUATION

  • After each turn, the questioner recommends 10 films; an LLM-as-judge scores them against the hidden profile, and mean ratings are reported across 200 users over five turns.Inconsistent recommendations are removed and replaced; each score ranges from 1 to 5 in 0.5 increments and includes a brief justification.Source: §I.2 · p. 30

I.3 ALGORITHMIC DETAILS

  • BED-LLM and Entropy compare 8 candidate questions per turn and aim to generate 5 candidate hypotheses for preference elicitation.Unconstrained question generation is used because profiles can be diffuse and a small set of hypotheses can be easy to split.Source: §I.3 · p. 31
  • Data–estimation is not viable for this preference task because variable-length, high-token-count θ samples make the required entropy infeasible to estimate and not meaningful.Source: §I.3 · p. 31

Related papers

Loading 2508.21184v3…