Skip to content

Conformal Information Pursuit for Interactively Guiding Large Language Models

🕒 Published (v1): 2025-01-01 · Source: NeurIPS · Venue: NeurIPS 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

LLM output probabilities are miscalibrated, making entropy-based query selection in interactive question-answering unreliable. This paper proposes Conformal Information Pursuit (C-IP), which replaces conditional entropy estimation with the average size of conformal prediction sets as a distribution-free uncertainty proxy. C-IP achieves better predictive accuracy and shorter query chains than standard Information Pursuit on 20 Questions and competitive performance on interactive medical QA (MediQ).

Problem

Interactive LLM agents that sequentially select queries to resolve uncertainty (Information Pursuit / IP) rely on conditional entropy estimates from LLM token logits. LLM probabilities are systematically miscalibrated (over/under-confident), producing flat, uninformative entropy curves that yield suboptimal query ordering and degraded prediction accuracy. Accurate mutual information estimation for LLMs is therefore intractable in practice.

Method

C-IP replaces entropy minimization with minimization of the expected log-size of conformal prediction sets. The key steps are:

  1. Theoretical link: Invoke Correia et al.'s result that H(Y|X) ≤ λ_α + (1−α_N) log E[|C_τ̂(X)|], bounding conditional entropy above by expected prediction-set size when marginal coverage (1−α) is guaranteed.
  2. Conformal sets: Use Split Conformal Prediction (SCP) on a held-out calibration set to construct prediction sets C_τ̂(k) for each query-chain length k (via "length marginalization" over random histories, avoiding intractable conditioning on specific chain realizations).
  3. History sampling: For closed query sets, histories are sampled uniformly (Uniform Parameterization); for open query sets, histories are sampled via LLM Direct Prompting simulations.
  4. Query selection: At each iteration k, select the query minimizing log E[|C_τ̂(k+1)(q(X))| | q₁:k(x_obs)], estimated empirically.
  5. Stopping: Halt when the std. of estimated entropy across candidate queries falls below threshold ε.

Key Contributions

  • Formal connection between conformal prediction set size and conditional entropy, applied to sequential information gain for LLMs.
  • C-IP algorithm with two tractable history-sampling strategies (uniform and LLM-simulated) to construct length-marginalized conformal sets.
  • Empirical demonstration that conformal prediction set sizes produce monotonically decreasing, informative uncertainty curves where LLM logit-based entropy does not.
  • Application to interactive medical diagnosis (MediQ) with interpretable query-answer chain generation.
  • Comparison against probability calibration baselines (Platt Scaling, Temperature Scaling) and state-of-the-art reasoning method UoT.

Results

  • 20 Questions (Llama-3.1-8B, closed query set, binary answers): C-IP outperforms IP and Random at every iteration; IP-based methods sharply dominate random selection.
  • 20 Questions (open query set, free-text answers): C-IP (α=0.15) outperforms both IP and Direct Prompting baselines at all iterations.
  • vs. UoT (open query set, binary answers): UoT accuracy 0.57 ± 0.13 (avg. 13.57 queries) vs. C-IP 0.37 ± 0.11 (avg. 11.87 queries) — UoT wins on accuracy with binary answers.
  • vs. UoT (open query set, free-text answers): C-IP accuracy 0.83 ± 0.05 (avg. 10.58 queries) vs. IP 0.65 ± 0.18 (avg. 10.04 queries) — C-IP achieves ~45% accuracy improvement over IP.
  • MediQ (Internal Medicine, Pediatrics, Neurology): C-IP achieves accuracy comparable to IP and competitive with non-sequential (single-turn) baselines; valid conformal coverage on IM and Pediatrics, undercoverage on Neurology (small calibration set, n=36).
  • vs. Platt Scaling / Temperature Scaling: C-IP matches or outperforms calibrated-IP variants, particularly for binary queries with open query sets.

Limitations

  • Length marginalization relaxes the ideal guarantee: Coverage is over the distribution of random query chains, not the specific chain produced at test time; full conditional risk control is left as future work.
  • Calibration set dependence: Performance degrades when calibration sets are small (Neurology with n=36 undercovers); coverage is only marginally valid.
  • Closed-query-set construction for MediQ: Per-datapoint query sets built from ground-truth context facts, which may not reflect realistic deployment where the full context is unavailable.
  • UoT superiority on binary answers: Multi-step lookahead (UoT) outperforms the greedy C-IP for binary query settings, suggesting immediate-reward greedy approaches have limits.
  • Experiments limited to small open-source models (7–8B parameter range); scalability to larger or closed models not evaluated.
  • Binary vs. free-text asymmetry: Coverage is less stable for open query sets in early iterations due to large candidate query diversity.

Relevance to Agentic AI / LLM Agents

C-IP directly addresses a core challenge in LLM-based agentic loops: deciding which information to seek next when operating under uncertainty. The framework formalizes multi-turn information-seeking as a sequential decision problem and provides a principled, calibration-robust stopping criterion — both critical for agents that must balance query cost against prediction confidence. By replacing miscalibrated logit-based uncertainty with distribution-free conformal sets, C-IP offers a plug-in improvement to any agentic architecture that uses IP-style query selection (e.g., diagnostic agents, tool-calling agents, clarification-seeking dialogue systems). The MediQ results demonstrate that interpretable, step-by-step reasoning traces can emerge naturally from the query chain, which is relevant for explainable agentic decision-making in high-stakes domains.