Cold-start personalization requires inferring user preferences through interaction when no user-specific historical data is available. The core challenge is a routing problem: each task admits dozens of preference dimensions, yet individual users care about only a few, and which ones matter depends on who is asking. With a limited question budget, asking without structure will miss the dimensions that matter. Reinforcement learning is the natural formulation, but in multi-turn settings its terminal reward fails to exploit the factored, per-criterion structure of preference data, and in practice learned policies collapse to static question sequences that ignore user responses. We propose decomposing cold-start elicitation into offline structure learning and online Bayesian inference. Pep (Preference Elicitation with Priors) learns a structured world model of preference correlations offline from complete profiles, then performs training-free Bayesian inference online to select informative questions and predict complete preference profiles, including dimensions never asked about. The framework is modular across downstream solvers and requires only simple belief models. Across medical, mathematical, social, and commonsense reasoning, Pep achieves 80.8% alignment between generated responses and users' stated preferences versus 68.5% for RL, with 3-5x fewer interactions. When two users give different answers to the same question, Pep changes its follow-up 39-62% of the time versus 0-28% for RL. It does so with ~10K parameters versus 8B for RL, showing that the bottleneck in cold-start elicitation is the capability to exploit the factored structure of preference data.
Figures & tables
Figure 1: Overview of Pep . Offline: We learn a structured world model from population data capturing preference correlations through latent user embeddings. Online: For new users, we adaptively select questions, update beliefs after each response, and predict the full preference profile, including preferences not asked about, to generate personalized responses.
Table 2Figure 3
GRPO (Fixed Sequence)
Pep (Adaptive)
Turn
Criterion
User A (casual)
User B (formal)
User A Criterion
Resp.
User B Criterion
Resp.
Q1
Conversational Tone
5
1
Conversational Tone
5
Conversational Tone
1
Q2
Academic Citations
no pref
no pref
Humor/Wit
4
Formal Definitions
5
Q3
Technical Terminology
1
3
Real-World Examples
5
Structured Format
4
Q4
Abstract Principles
no pref
2
Storytelling
3
Comprehensive Coverage
5
Q5
Theoretical Framework
no pref
no pref
Analogies
no pref
Precise Language
3
Table 3: Qualitative comparison on CSQA. Users with opposite preferences (User A: casual, engaging; User B: formal, thorough) answer questions about “Why might someone walk to work instead of driving?” Ground-truth preference shown in green (User A) and blue (User B). GRPO asks identical questions; Pep adapts to responses. Scale: 1=strongly avoid, 5=strongly prefer.
Figure 4: Ablation study on (i) modeling preference correlations: without the latent structure that captures correlations between preferences (red), elicitation yields very slow improvement over population average, compared to modeling preference correlations (blue, gray); and (ii) adaptive querying: adaptive selection (blue) closes 24% of the gap at T=5 , outperforming random querying (gray) at T=6 , effectively saving one question.
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Strategy
MedQA
AIME
SocialIQA
CSQA
Random
4.43 ±0.02
4.36 ±0.04
4.34 ±0.03
4.32 ±0.03
InfoGain
4.44 ±0.01
4.34 ±0.04
4.34 ±0.03
4.33 ±0.02
InfoGain-Soft
4.44 ±0.02
4.36 ±0.03
4.34 ±0.03
4.31 ±0.03
Uncertainty
4.44 ±0.01
4.33 ±0.03
4.34 ±0.03
4.32 ±0.02
Uncertainty-Soft
4.44 ±0.02
4.37 ±0.02
4.35 ±0.04
4.32 ±0.03
Appendix
Table 4: Acquisition strategy ablation showing raw judge scores (1–5 scale) at T=5 . Bold indicates best per dataset. Mean ± std over 20 trials. Stochastic variants (Soft) often match or outperform greedy selection due to added exploration.
An agent that learns a user's preferences from their choices faces a cold start problem: before any choices are observed, it must rely solely on a prior. Informative priors are usually fitted to historical choice data, which new tasks and deployments lack. To address this, we present Agentic-Priors, which lets agentic systems use the implicit knowledge of large language models (LLMs) instead. Specifically, an LLM states a new user's trade-offs in interpretable terms, such as willingness to pay or value of time, which we map to a prior over multinomial logit coefficients. This prior is then refined by a Bayesian learner as choices are observed. Across seven choice datasets, Agentic-Priors improves cold start accuracy over an uninformed prior by 5-40 percentage points. It also outperforms AutoElicit, a state-of-the-art LLM prior-elicitation method, on three datasets and loses on one. It is up to 18 points more accurate than in-context learning, and never significantly worse. Against hierarchical Bayes models fitted to surveys of increasing size, our approach is worth roughly 6-40 surveyed users, in terms of log-loss, so its value is concentrated in a deployment's first users.
Bruno Arcanjo, Zhaoxing Li, Sebastian Stein
University of Southampton, Southampton, United Kingdom
Large language models can answer the same question in different styles, but users' preferred styles are hidden and vary across users and questions. We study inference-time personalization through online selection from a fixed set of prompts, each representing a persona. Users arrive sequentially, each asks a short sequence of questions, and the system displays two responses per question and observes one pairwise choice. We formulate this interaction as a variant of the contextual dueling bandit problem in which the learner starts without preference data, adapts within each session, and exploits information shared across users. The objective is to minimize cumulative strong regret, summing the utility gaps of both displayed responses relative to the user's best response among the available options. We make two contributions. First, we introduce the problem and release a reproducible preference benchmark and dataset built around a tutoring case study, containing educational questions, LLM-generated answers in six teaching styles, and pairwise judgments from LLM-simulated students with hidden preference profiles. We fit Bradley-Terry models to these judgments to obtain reference utilities for regret evaluation. Second, we propose a baseline that learns a mixture prior over users from completed sessions and adapts to each new user within the session. On students and topics never used in development, it removes 44-48% of random pairs' excess regret and achieves over half the performance of a per-user linear oracle fitted in hindsight. We release code, prompts, and the benchmark.
Personalized language models aim to adapt responses to individual users, whose preferences are often latent and revealed gradually through interaction. Existing training-free methods rely on stored histories or retrieved memories, but they often struggle to reconcile long- term preferences with short-term topic-specific needs. To address this issue, we propose HyperTrace, a training-free framework that formulates online personalization as latent preference tracing. HyperTrace maintains interpretable natural-language hypotheses over short-term intent and long-term preferences, and updates them through an SMC-style reweight process using an LLM-based surrogate choice model. By updating these hypotheses across turns and sessions, HyperTrace enables personalization without parameter updates. Experiments on PRISM and PersonaMem-v2 show that HyperTrace improves response alignment, preference prediction, and profile consistency over strong online baselines, demonstrating the effectiveness of tracing latent user preferences for robust personalization. Code and scripts are available in the repository: https://github.com/jiseshen/HyperTrace.
Jianzhi Shen, Keyu Mao, Minghao Shao +7
Johns Hopkins University · Institute of Science Tokyo · NYU Tandon +1