Asking Again: Drift-Aware Information-Gain Elicitation over Catalog Prefix Trees

A shopping or travel assistant has to work out what a person wants by asking questions. The best-founded way to choose those questions scores each candidate by expected information gain: how much, on average, the answer will shrink the agent's uncertainty about the user's goal. Methods built on this score assume the goal stays fixed during the conversation. They also assume the goal is one of a few dozen candidates the agent can enumerate. Real users break both assumptions. They change their minds. They form new requirements only after seeing an option. And the catalog they choose from may hold a million products. When the goal moves, an agent that assumes a fixed target becomes confidently wrong. It never asks about an attribute again once it thinks it knows the answer.

We propose an agent that does two things. First, it holds its belief about the user's goal on a prefix tree, the compressed structure that pattern mining uses to store millions of transactions by sharing common prefixes, so information gain can be computed exactly over the whole catalog. Second, it updates that belief with a drift model in which each preference attribute has its own rate of going stale, and that rate rises when the agent has just shown the user something that tends to provoke a new requirement. Under this model, re-asking a stale attribute or deliberately showing an item becomes an action whose information value the agent can compute. Nothing has to be added as a heuristic. The test bed is AcCoRD and WebShop, where current agents fail most clearly on exactly these behaviors.

Core Claim

Information-gain question selection becomes robust to preference drift without extra machinery if the drift is written into the belief update rather than bolted onto the evidence weights. The drift should be per attribute and conditioned on what the user has been shown, not a single uniform forgetting rate. A catalog prefix tree makes this exact and cheap at million-item scale. It does so because the tree already stores which attribute combinations actually exist, and the drift update needs those conditional distributions.

Concretely, let $\theta = (\theta_1,\dots,\theta_m)$ be the user's target, a joint assignment of values to $m$ attributes such as category, size, color, material and price band. Let $b_t(\theta)$ be the agent's belief after turn $t$, and let $p_0$ be the catalog prior read off the prefix tree. Between turns, attribute $a$ "resets" with probability $\rho_a(s_t)$, which depends on the item or option $s_t$ the agent just surfaced:

$$b_{t}^{-}(\theta) = \big(1-\rho_a(s_t)\big)\, b_t(\theta) + \rho_a(s_t)\, b_t(\theta_{-a})\, p_0(\theta_a \mid \theta_{-a}).$$

Here $b_t(\theta_{-a})$ is the belief marginalized over attribute $a$, and $p_0(\theta_a \mid \theta_{-a})$ is the catalog's conditional distribution of $a$ given the other attributes. The operation is applied for each attribute.

The next action $q$ maximizes expected information gain under $b_t^{-}$. An action is either a question or the act of showing an item. Expected information gain is $H(\theta) - \mathbb{E}_{A}[H(\theta \mid q, A)]$, where $H$ is Shannon entropy and $A$ is the user's possibly noisy response.

Two consequences follow from this form. Because stale attributes flow back toward the prior, the entropy over them grows with time since they were last confirmed, so re-asking regains value without any rule saying so. And because $\rho_a$ depends on $s_t$, showing an item that historically provokes a new constraint on attribute $a$ carries information about $a$. That is the mechanism AcCoRD's triggered preferences need.

Where This Sits

The questioning side is supplied by three methods. BED-LLM runs sequential Bayesian experimental design with an LLM. It samples roughly fifteen hypotheses, estimates information gain with a Rao-Blackwellized estimator, and improves 20-Questions success by an average of 37.4 percentage points over direct prompting. CA-BED adds soft likelihoods and multi-step lookahead over a question/evidence tree. Adaptive Querying with AI Persona Priors uses a finite persona dictionary to get closed-form posterior updates.

All three assume a stationary target over a small, flat candidate set. The persona-prior paper also supplies the main constraint on our design. It reports that misspecified adaptive questioning becomes overconfident in wrong answers, and that static question batteries can be more robust in long dialogues. We read this as evidence that the posterior collapses because nothing in the model lets it uncollapse. Our drift term is aimed directly at that failure. If it does not help, that finding stands against us.

The drift side is motivated by Right Now, Wrong Then. NS-DPO weights offline preference pairs by $\gamma^{T-t_i-1}$ and shows that stationary DPO reward accuracy falls to near-random (about 50–55%) after preference flips. The paper also notes that one uniform $\gamma$ cannot tell an obsolete preference from a still-valid old one, and that the right $\gamma$ depends on an unknown amount of drift. Our per-attribute, exposure-conditioned hazard is the online, belief-level answer to both limitations.

Teaching Language Models to Evolve with Users (RLPA) shows that an explicit slot-value profile lets a trained agent track mid-conversation changes over 70 turns. Our belief is a probabilistic version of that profile, with an explicit drift law instead of a learned one.

AcCoRD supplies the problem. Its triggered preferences only exist once the agent surfaces a relevant option. On these, scores fall as low as 0.09, while underspecification scores sit at 0.7–0.9. AcCoRD's uncertainty-prompting method, UncReAct, does not fix this.

The pattern-mining side supplies the representation and the hazard estimates. FP-Growth-style conditional projection, as analyzed by Panda et al., and prefix-sharing compression, reported by Hoffmann et al. at roughly one-sixth the memory of lists, let the catalog prior and its conditionals live in one structure. We change what the nodes store. They hold belief mass instead of support counts. Pruning is soft, following CA-BED's lesson about noisy answers, rather than the hard support- or utility-bound pruning used by TMKU.

The exposure hazards $\rho_a(s)$ are estimated by mining sequential patterns of the form "option with attribute X shown → user adds or revises a constraint on Y" from interaction logs. We use the relaxed temporal matching of RASP, because turn gaps between exposure and reaction vary. RASP and similar miners have only ever run on passive logs. Here their output becomes a parameter of an active questioner.

Research Program

The first component is the belief tree. We build an FP-tree over WebShop's 1.18M products, with attributes ordered by global frequency. Each node stores the prior mass and the current posterior mass of its subtree. A yes/no or multiple-choice answer about attribute $a$ multiplies the masses of nodes at $a$'s level by soft answer likelihoods, then propagates sums upward. Information gain for a question on $a$ needs only the masses aggregated over nodes at that level, so its cost scales with the number of tree nodes, not the number of items. We will measure that node count against catalog size, since dense attribute combinations are the known weak point of prefix trees. The drift update needs $p_0(\theta_a \mid \theta_{-a})$, which the tree provides by conditional projection. We will deliver this as an exact procedure for the reset operation, with a sampled fallback if the cost of marginalizing a deep attribute dominates.

The second component is drift and exposure modeling. Per-attribute base hazards are fit by maximum likelihood on training-split dialogues in which constraints get revised. Exposure-conditioned hazards come from sequential patterns mined on logs. To build those logs, we run an exploratory agent that surfaces random options on AcCoRD training scenarios, record when the simulated user produces a new constraint, and mine those episodes. Evaluation uses held-out scenarios only. We will report how many mined patterns transfer across scenarios, because simulator-specific patterns are the obvious way this could fool us.

The third component is natural-language grounding. An LLM maps user utterances to soft likelihoods over attribute values, as CA-BED does. It also renders the selected attribute question or item display as a turn. The information-theoretic choice itself is made outside the LLM, following the finding of Uncertainty of Thoughts that explicit entropy signals beat LLM self-reflection for choosing queries.

Baselines

The naive reference point is direct prompting of the same backbone LLM with the full dialogue history. We also include AcCoRD's UncReAct prompting, run through AcCoRD's own harness with identical turn budgets. Beating it means higher per-category scores at no more turns.

The strongest existing elicitation method is BED-LLM. It samples candidate hypotheses from the LLM, filters them for consistency with the history, and picks the question with maximal estimated information gain. It is the strongest competitor because it is the only cited system that already does principled information-gain selection for preference elicitation, on MovieLens-100K. We give it the same backbone, the same candidate-question generator, and a matched wall-clock budget per turn. Under that budget it may use more sampled hypotheses than its default fifteen. For WebShop-scale catalogs we also give it retrieval from the catalog, so it does not handicap itself by sampling nonexistent products. No reported result found on Lacuna for BED-LLM on AcCoRD or WebShop, so we run it ourselves. We count it as beaten if our agent improves the per-category score on in-session drift and triggered preferences, with confidence intervals over held-out scenarios that do not overlap, at equal turns.

For context on trained agents, we include RLPA via its public code (RLPA), which reports 73.38 on Vanilla ALOE. We train it on the same training scenarios. For the WebShop task-completion numbers, the reference is the best IL+RL agent from WebShop, at 29.1% success, score 62.4, and option-selection score 38.9, against 73.9 for humans.

The ablations isolate the key ingredient. We compare four variants of our own agent: no drift ($\rho = 0$); a uniform NS-DPO-style decay with one tuned $\gamma$ applied to all past evidence; per-attribute hazards without exposure conditioning; and the full model. Every hazard and $\gamma$ is tuned on the same validation split with the same number of trials. Separately, the flat-versus-tree comparison swaps the prefix tree for a sampled flat candidate set of the same compute cost. This shows whether the tree buys anything beyond the drift model.

Why not just…?

Why not just add exponential forgetting to BED-LLM's posterior? This is the most serious alternative, and it is the uniform-$\gamma$ ablation. NS-DPO's own analysis says the best $\gamma$ depends on an unknown amount of drift, and that uniform discounting cannot keep a still-valid old answer, such as shoe size, while dropping an obsolete one, such as price tolerance. That argues for per-attribute hazards. But it is an argument, not a measurement. If uniform forgetting matches our agent on the drift-injected WebShop task, we will say the per-attribute structure is unnecessary there. In that case the remaining claim rests on triggered preferences, where uniform forgetting has no mechanism to make showing an item informative.

Why not just use a factorized belief with one independent distribution per attribute, and no tree? Information gain is trivial to compute under independence. The trouble is that the reset step needs $p_0(\theta_a \mid \theta_{-a})$, and catalogs have strong dependencies: valid sizes depend on the category, materials on the product type. Under independence, the agent asks about combinations that do not exist and resets toward them. We include the factorized model as a baseline. If it ties the tree on AcCoRD, which has only about 11 preferences per travel scenario, the tree's value is confined to catalog-scale settings, and we will scope the claim to those.

Why not just let a strong LLM or a trained profile tracker like RLPA follow the drift in context? AcCoRD reports Claude-4.5 below 30% perfect outcomes. Uncertainty prompting there leads weaker models to over-ask. RLPA tracks explicitly revealed changes well, but it has no notion of which stimulus would provoke an unrevealed preference, and that case is where scores reach 0.09. Running RLPA on the same split settles whether learned tracking already closes the triggered-preference gap.

Why not just detect a change point and restart the posterior? Global restarts throw away every still-valid attribute. Our per-attribute reset contains the restart as the special case where every hazard equals 1. We add a change-point-restart variant, with a tuned detection threshold, to the drift experiment.

Proposed Experiments

The first experiment tests computation at scale. We sample WebShop target products, simulate noisy attribute-level answers, and compare exact tree-based information gain against flat sampling with 15, 100 and 1,000 hypotheses. Metrics are agreement on which question to select, turns to identify the target, and per-turn latency. The decisive check is whether flat estimates pick a different question often enough to cost turns at matched compute. If they rarely do, the tree is an efficiency detail, not a contribution.

The second experiment tests in-session drift. We use WebShop instructions with injected change points, following NS-DPO's sudden-flip and gradual-drift protocols: a target attribute's value changes at a random turn, and the simulated user reveals the change only when asked about that attribute or shown a conflicting option. We report final purchase success, option-selection score, and how often the agent asks about an already-confirmed attribute again. The decisive check is that the full model re-asks mostly the attributes that actually drifted. A higher re-ask rate alone does not count.

The third experiment tests triggered preferences. We run AcCoRD-Shop and AcCoRD-Travel on held-out scenarios and report scores per category: hard, soft, unachievable and triggered. The decisive check is the triggered category. The full model must beat both the per-attribute-hazard ablation and BED-LLM there, while staying within the 0.7–0.9 range already reached on underspecification and using no more turns. We will also report what happens when the mined exposure patterns are replaced by shuffled ones. If shuffled patterns perform equally well, the gain comes from showing more items, not from pattern mining, and we will report that as the finding.