HorizonBench: Long-Horizon Personalization with Evolving Preferences

1. Problem Definition: Long-Horizon Personalization

The paper addresses a critical gap in Large Language Model (LLM) personalization: tracking user preferences that evolve over extended timelines due to life events.

• The Core Challenge: Current personalization systems often treat user preferences as static traits. However, in real-world interactions (e.g., a user becoming a CEO, experiencing a health crisis, or changing relationship status), preferences shift dynamically.
• The Specific Failure Mode: The authors identify a specific failure called "belief-update failure." This occurs when a model correctly retrieves a user's historically stated preference but fails to update it based on intervening life events. The model anchors on outdated information rather than inferring the current state.
• Data & Measurement Gap: Existing benchmarks lack the "ground-truth provenance" needed to diagnose why models fail. Real-world data cannot reveal the causal link between a life event and a preference change, and existing synthetic data lacks structured causal models of evolution.

2. Methodology

A. The Data Generator: Mental State Graph

To solve the data gap, the authors introduce a state-first data generator that inverts the standard approach. Instead of inferring mental states from conversations, it generates conversations from a structured Mental State Graph ($G$).

• Structure: The graph maintains a user's persona, social connections, life events, and preferences.
• Causal Evolution: Preferences are linked via typed dependency edges (e.g., a career change $\to$ work preferences $\to$ communication style). When a life event occurs, it triggers a cascade of preference updates through these edges.
• Provenance: Every preference change is recorded with its triggering event and timestamp, creating a ground-truth timeline of evolution.
• Conversation Generation:
  • Event Sampling: Events are sampled based on agent states and history to ensure realism.
  • Expression Tracking: The system distinguishes between when a preference evolves (internally) and when it is expressed (verbally). Preferences can evolve without being restated, creating "stale" preferences that require inference.
  • Variants: The generator produces Explicit (direct statements) and Implicit (contextual cues) variants to test different levels of difficulty.

B. The Benchmark: HORIZONBENCH

Constructed from the generator, HORIZONBENCH is a diagnostic benchmark designed to isolate retrieval from belief updating.

• Scale: 4,245 items derived from 360 simulated users, covering 6-month timelines with an average of 4,300 turns (163K tokens) per user.
• Task Format: A 5-option multiple-choice question embedded in a long conversation history. The model must select the assistant response that aligns with the user's current (evolved) preference.
• Hard-Negative Distractors: Crucially, one of the incorrect options is the pre-evolution value (the user's original preference). This forces the model to choose between the outdated fact and the updated state.
• Validation Filter: A 5-LLM consensus filter ensures that items cannot be answered correctly without the full conversation history. If 5 validation models (without history) cannot distinguish the correct answer, the item is retained.

3. Key Contributions

1. State-First Data Generator: A novel framework that constructs conversations from a structured mental state graph, providing ground-truth provenance for every preference change across 6-month timelines.
2. HORIZONBENCH Benchmark: A large-scale, diagnostic benchmark featuring:
   • Pre-evolution hard-negative distractors.
   • Controlled dimensions: Evolution status (static vs. evolved), expression explicitness (implicit vs. explicit), and context length.
   • Rigorous filtering to ensure history dependence.
3. Identification of Belief-Update Failure: The paper empirically demonstrates that the primary bottleneck in long-horizon personalization is not just memory retrieval, but the inability to update beliefs based on new state information.

4. Experimental Results

The authors evaluated 25 frontier models (including Claude, Gemini, and OpenAI families) on the 4,245 items.

• Overall Performance: The best model, Claude-opus-4.5, achieved only 52.8% accuracy. Most models scored at or below the 20% chance baseline (random guessing on 5 options).
• Belief-Update Failure Analysis:
  • Distractor Selection: When models answered incorrectly on evolved items, they selected the pre-evolution distractor (the outdated value) significantly more often than chance (approx. 38% of errors vs. 25% expected). This indicates a strong anchoring bias on the original stated preference.
  • Evolved vs. Static Gap: All 25 models performed significantly worse on evolved preferences compared to static ones (average drop of 2.7 percentage points), confirming that preference change introduces a difficulty beyond simple long-context recall.
• Controlled Experiments:
  • Context Length: Shortening the history (0–14 days) did not eliminate the failure; in fact, the gap between evolved and static performance widened. This proves the failure is not due to memory capacity limits but a lack of state-tracking logic.
  • Expression Explicitness: While implicit expression was harder overall, the belief-update failure persisted regardless of whether preferences were stated explicitly or implicitly.
  • Subtlety: Even when distractors were made less subtle (easier to distinguish), models still anchored on outdated preferences.

5. Significance and Implications

• Diagnostic Capability: HORIZONBENCH is the first benchmark capable of distinguishing between retrieval failure (model didn't find the info) and belief-update failure (model found the info but didn't update it).
• State Tracking as a Bottleneck: The results suggest that current LLMs are "state-blind." They excel at retrieving facts but fail to maintain a coherent, evolving mental model of a user's state over time.
• Future Directions: The paper argues that improving long-horizon personalization requires:
  • Explicit preference state representations that are updated upon life events.
  • Retrieval strategies that surface not just stated preferences, but the events that may have invalidated them.
  • Architectures capable of "Theory of Mind" reasoning to infer state changes from context.

In summary, HORIZONBENCH reveals that while LLMs are becoming better at long-context memory, they fundamentally struggle to update their understanding of a user when that user's life circumstances change, a critical limitation for building truly personalized AI companions.