STARK: Moving towards Personalized Agents That Truly Learn and Remember

Aryan Jain, Abhishek Jha, Anish Nediyanchath, Promod YenigallaarXiv 2026 · arXiv

TL;DR

STARK is a dual-graph memory architecture for LLM agents that separates "what happened" (episodic events) from "why it happened" (behavioral insights). By using events as edges to ground insights in evidence, STARK enables agents to truly learn from experience and even transfer knowledge between similar users to solve the "cold-start" problem.

What Problem Does This Paper Address?

As autonomous agents take on long-running tasks like vendor negotiations or complex workflow orchestration, they need to remember more than just a transcript of past chats. Current memory architectures (like standard RAG or flat knowledge graphs) typically treat events, preferences, and goals as undifferentiated nodes.

This leads to two major issues:

  1. Redundant Reasoning: The agent must re-derive a user’s preferences or constraints from raw history every time a query is made, which is computationally expensive and often inconsistent.
  2. The Cold-Start Silo: Knowledge is usually siloed per user. A new agent (or a new user) starts with zero knowledge, even if their goals are identical to those of a seasoned veteran.

STARK aims to move agents from simply "recording" to actually "remembering and learning" by distilling durable behavioral signals from individual episodes.

Methods

The core of STARK is its dual-graph architecture, which splits memory into two interconnected layers:

  • Episodic Graph ($G_E$): A factual record of interactions, milestones, and entities (Users, Organizations, etc.), linked temporally and causally.
  • Insight Graph ($G_I$): A layer of behavioral signals—preferences, goals, and constraints—distilled by an LLM.

The "aha!" innovation here is the event-as-edge bridge. Instead of just linking nodes, episodic identifiers serve as typed edge labels in the Insight Graph. This ensures every insight is grounded in the specific events that produced it, allowing for bidirectional navigation between a high-level preference and its raw evidence.

Figure 1: From scattered multi-session dialogue to grounded cold-start personalization. In the example shown, Bob tries different strategies with vendors ACME and NEXUS. The graph built for Bob, helps Eve (a new account manager) to close deal with their vendor using proven techniques. Baseline graph buries preferences while our dual-graph memory separates episodes and insights (evidence-bearing nodes, strength shown as border thickness), with the same event as an edge label bridging them.

To handle multiple users, STARK projects these graphs into a relational embedding space using TransR. By "unprefixing" behavioral signals (treating a "preference for soft negotiation" as a shared concept) while "prefixing" user-specific entities, the system creates a geometry where users with similar "preference fingerprints" cluster together. This allows a new user to inherit likely insights from similar peers via link prediction.

Datasets

The authors evaluated STARK across five public benchmarks and one real-world production deployment:

  • LoCoMo & LongMemEval: Focused on long-horizon conversational memory and temporal reasoning.
  • RealPref & PAL-Bench: Focused on explicit preference extraction and ranking.
  • LongLaMP: A benchmark for personalized abstract generation, used here to test cross-user transfer in a cold-start setting.
  • Production Pilot: An 8-week A/B test involving 40 Amazon account managers handling vendor negotiations.

Key Insights and Ideas

  • Insight Saturation: While episodic nodes grow linearly with time, insight nodes eventually saturate as the agent "learns" the user. This keeps the retrieval surface small and efficient even as the interaction history grows (see Figure 3).
  • Evidence-Ranked Retrieval: STARK doesn't just retrieve; it ranks insights using evidence vectors that track the number of supporting episodes, outcome success (did the tactic work?), and consistency.
  • Privacy-Preserving Transfer: The cross-user mechanism allows a "cold-start" user to benefit from the collective experience of the graph without ever accessing another user's raw interaction text or episodic records.
Figure 3: Per-dataset graph growth with ingested sessions. Episodic nodes GE (solid) grow roughly linearly; insight nodes GI (dashed) saturate as recurring signals merge in place, keeping the retrieved surface small as history accumulates.

Key Results

STARK demonstrated significant improvements over state-of-the-art memory systems like Mem0 and MAGMA:

  • Benchmark Performance: STARK improved judge scores by 1.48 points on LongMemEval information extraction and 0.93 points on LoCoMo open-domain questions.
  • Cold-Start Recovery: On the LongLaMP benchmark, at extreme 5% graph sparsity, cross-user transfer recovered 1.5x quality (2.0/5 score) compared to text-only baselines (1.3/5).
  • Real-World Impact: In the vendor-negotiation pilot, STARK cut negotiation rounds per deal by 18% and reduced total cycle time by 15%. New hires saw the biggest gains, effectively "borrowing" the expertise of experienced managers through the graph.

Limitations and Future Work

The authors acknowledge several areas for improvement:

  • Embedding Capacity: The TransR projections have a fixed capacity; as the graph becomes extremely dense, the quality of the relational embeddings may degrade.
  • Privacy Guarantees: While the system is designed to prevent raw data leakage, it lacks formal differential privacy guarantees against membership inference attacks on the aggregate fingerprints.
  • Future Planning: The authors suggest using these behavioral paths as a search tree for MCTS-style (Monte Carlo Tree Search) rollouts, allowing agents to simulate and choose the interaction trajectory most likely to reach a user's goal.

Summary updated

Abstract

Long-term memory is essential for personalized agentic systems that interact with users over long time periods, yet current architectures only capture what happened while leaving the reasoning of why it happened to be derived later by underlying LLMs.%, and silo knowledge within individual users. These events can, however, convey not only what a user experienced but also how that experience shaped their behavioral patterns. We introduce STARK, a dual-graph memory architecture which treats these events not just as nodes but also as edges between behavioral insights. STARK maintains an Episodic Graph which records interactions as temporally, causally, and semantically linked episodes; and an Insight Graph which represents LLM-extracted behavioral signals scored by how many events support them, connected by the very events that led to them. At inference, behavioral knowledge is retrieved directly from insight nodes grounded by event-as-edges, eliminating repeated episodic traversal. The event-as-edge structure also naturally enables projecting the knowledge graph into a relational embedding space where cross-user transfer becomes possible under shared contextual circumstances, allowing the system to infer missing insights for cold-start users. Evaluations show that STARK improves by 1.48 judge score on LongMemEval information extraction and 0.93 on LoCoMo open domain questions over state of the art. On the public LongLaMP abstract-generation benchmark, cross-user transfer improves open-ended judge scores by 0.7 points and ROUGE-L by 3 at 5% graph sparsity.
BibTeX
@misc{jain2026stark,
  author = {Aryan Jain and Abhishek Jha and Anish Nediyanchath and Promod Yenigalla},
  title = {{STARK: Moving towards Personalized Agents That Truly Learn and Remember}},
  year = {2026},
  eprint = {2611.25705},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.25705},
}
Figure