StateTree: Enhancing Long-Term Dialogue Reasoning via Reinforcement Learning

# StateTree: Enhancing Long-Term Dialogue Reasoning via Reinforcement Learning
Source: [https://arxiv.org/html/2609.38809](https://arxiv.org/html/2609.38809)
Naen Xu††thanks:˜Equal contribution\.Affiliation:Zhejiang UniversityAffiliation:Taobao & Tmall Group of AlibabaEmail:[xunaen@zju\.edu\.cn](mailto:)Yibo Hu††thanks:˜Project leader\.Affiliation:Taobao & Tmall Group of AlibabaEmail:[zjradty@zju\.edu\.cn](mailto:)Shixin HongAffiliation:Taobao & Tmall Group of AlibabaEmail:[cuiwanqing\.cwq@taobao\.com](mailto:)Hengyu AnAffiliation:Zhejiang UniversityEmail:[boxuan\.hyb@taobao\.com](mailto:)Meiguang JinAffiliation:Taobao & Tmall Group of AlibabaEmail:[hongshixin\.hsx@taobao\.com](mailto:)Junfeng MaAffiliation:Taobao & Tmall Group of AlibabaEmail:[meiguang\.jmg@taobao\.com](mailto:)Tianyu Du††thanks:˜Corresponding author\.Affiliation:Zhejiang UniversityEmail:[jack\.majf@taobao\.com](mailto:)

###### Abstract

Large language models deployed as personalized assistants must reason over long, evolving interaction histories\. However, in long\-term dialogue reasoning, relevant evidence is scattered across sessions, preferences may be revised over time, and standard long\-context training fails to address these challenges under data scarcity and prohibitive computational costs\. We propose StateTree, a data\-driven RL method that constructs a challenging auxiliary task from scarce dialogues with verifiable ground truth\. StateTree augments multi\-session dialogues with a tree\-structured path\-tracing task: key\-value records are embedded across sessions to form a binary tree\. Solving the task requires the model to traverse from root to leaf by retrieving records across sessions and comparing timestamps to resolve branches, then recover the hidden target question among distractor leaves\. We apply curriculum RL training progressively increasing tree depth and introduce a compositional variant whose edges carry step\-level reasoning fragments, training the model to compose partial cues into coherent queries\. Trained on 10K\-token contexts, StateTree generalizes to 128K tokens without full\-length RL costs and exhibits capabilities including cross\-session retrieval, temporal reasoning, knowledge update, and compositional multi\-hop reasoning\. StateTree outperforms both SFT and RL\-based baselines while preserving short\-context general reasoning\. StateTree\-7B achieves gains up to \+23\.60% on LongMemEval \(128k\), and StateTree\-14B reaches 59\.00% accuracy on LongMemEval, surpassing QwenLong\-L1\-32B \(45\.20%\)111Code and dataset are available at[https://github\.com/bluedream02/StateTree](https://github.com/bluedream02/StateTree)\.\.

## 1Introduction

Large Language Models \(LLMs\) are increasingly deployed as personalized assistants for writing\([Mysore et al\., 2024](https://arxiv.org/html/2609.38809#bib.bib6);[Tian et al\., 2024](https://arxiv.org/html/2609.38809#bib.bib7)\), recommendation\([Hua et al\., 2023](https://arxiv.org/html/2609.38809#bib.bib8);[Li et al\., 2025c](https://arxiv.org/html/2609.38809#bib.bib40);[Li et al\., 2025b](https://arxiv.org/html/2609.38809#bib.bib41);[Chen et al\., 2024](https://arxiv.org/html/2609.38809#bib.bib42)\), and consultation\([Mysore et al\., 2024](https://arxiv.org/html/2609.38809#bib.bib6);[Xie et al\., 2024](https://arxiv.org/html/2609.38809#bib.bib9)\), while supporting long\-term, multi\-session dialogues\([Du et al\., 2025](https://arxiv.org/html/2609.38809#bib.bib27)\)\. However, LLMs struggle to leverage personal knowledge accumulated over extended interaction histories\([Zhong et al\., 2024](https://arxiv.org/html/2609.38809#bib.bib1);[Laban et al\., 2026](https://arxiv.org/html/2609.38809#bib.bib17)\), leading to degraded accuracy and reduced user satisfaction\([Ling et al\., 2025](https://arxiv.org/html/2609.38809#bib.bib4)\)\. While memory\-augmented systems\([Zhong et al\., 2024](https://arxiv.org/html/2609.38809#bib.bib1);[Fang et al\., 2026](https://arxiv.org/html/2609.38809#bib.bib2)\)improve personalization via compression, indexing, and retrieval over chat histories, they still rely on the backbone LLM’s reasoning ability\. Meanwhile, most long\-context research targets static documents\([Yang et al\., 2018](https://arxiv.org/html/2609.38809#bib.bib15);[Ho et al\., 2020](https://arxiv.org/html/2609.38809#bib.bib16)\), treating dialogue history as flat text and failing to adapt to evolving user personas\([Maharana et al\., 2024](https://arxiv.org/html/2609.38809#bib.bib12);[Wu et al\., 2025](https://arxiv.org/html/2609.38809#bib.bib11)\)\. Long\-term dialogue reasoning presents three challenges:

- •Data Scarcity \(ℂ​1\\mathbb\{C\}1\):Existing multi\-session datasets such as LoCoMo\([Maharana et al\., 2024](https://arxiv.org/html/2609.38809#bib.bib12)\)contain only 10 dialogues \(1540 QA pairs\), and LLM\-synthesized dialogues cannot guarantee answer correctness\.
- •Complex Dialogue Reasoning \(ℂ​2\\mathbb\{C\}2\):Unlike static documents, long\-term dialogues are non\-stationary: evidence is scattered across sessions with timestamps, and preferences may be revised later\. Answering question requires chaining multiple pieces of evidence, yet LLMs frequently fail at cross\-session retrieval, temporal reasoning, knowledge update, and multi\-hop composition\.
- •Prohibitive Computational Cost \(ℂ​3\\mathbb\{C\}3\):Training at near\-target context lengths\([Liu et al\., 2024a](https://arxiv.org/html/2609.38809#bib.bib20);[Li et al\., 2025a](https://arxiv.org/html/2609.38809#bib.bib18)\)incurs prohibitive compute costs and risks degrading short\-context and general reasoning abilities\([Peng et al\., 2023](https://arxiv.org/html/2609.38809#bib.bib19);[Shang et al\., 2025](https://arxiv.org/html/2609.38809#bib.bib3)\)\.

While synthetic trajectories for SFT\([Prabhakar et al\., 2025](https://arxiv.org/html/2609.38809#bib.bib28);[Liu et al\., 2025](https://arxiv.org/html/2609.38809#bib.bib29);[Chu et al\., 2025](https://arxiv.org/html/2609.38809#bib.bib36)\)mitigate data scarcity \(ℂ​1\\mathbb\{C\}1\), models trained on static traces show limited improvement and often fail to generalize to out\-of\-distribution datasets\. Reinforcement Learning \(RL\)\([Guo et al\., 2025](https://arxiv.org/html/2609.38809#bib.bib34);[Shao et al\., 2024](https://arxiv.org/html/2609.38809#bib.bib30)\)offers an alternative, yet its effectiveness in long\-term dialogue is constrained by the lack of challenging training data with ground truth \(ℂ​1\\mathbb\{C\}1\) and prohibitive costs of long interaction chains \(ℂ​3\\mathbb\{C\}3\)\. This leads to our central question:How can we elicit robustlong\-term dialogue reasoning\(ℂ​2\\mathbb\{C\}2\) from extremelyscarce data\(ℂ​1\\mathbb\{C\}1\) withoutprohibitive computational overheadof full\-context RL training \(ℂ​3\\mathbb\{C\}3\)?

![Refer to caption](https://arxiv.org/html/2609.38809v1/example.png)Figure 1:Model trajectories in multi\-session dialogue reasoning\. \(i\)QwenLong\-L1\-32B gets lost across sessions and misses information\.\(ii\) The StateTree\-trained model shows cross\-session retrieval, temporal reasoning, knowledge update, and multi\-hop reasoning, improving reasoning reliability\.In response, we introduceStateTree,a data\-driven RL pseudo\-task that constructs challenging synthetic auxiliary tasks embedded within authentic dialogues\. Our key insight is that multi\-session dialogue reasoning can be reframed as a path\-search problem: relevant evidence forms a navigable structure with temporal constraints and hierarchical dependencies\. These patterns can be taught through structured synthetic tasks that provide verifiable ground truth\.Concretely,StateTree embeds key\-value records into long\-term dialogues, transforming limited data into challenging training instances \(ℂ​1\\mathbb\{C\}1\)\. The same key is placed across multiple sessions with different timestamps, and the linked records form a binary tree\. The model must trace a path from root to leaf by comparing timestamps and following the most recent record at each branch point, until the leaf reveals the target question \(ℂ​2\\mathbb\{C\}2\)\.We apply a curriculum RL strategy that progressively increases tree depth and reasoning complexity; its final stage introduces a*Compositional StateTree*whose edges carry step\-level reasoning fragments that the model must aggregate into a coherent query\. By training at contexts of 10K tokens, StateTree avoids the prohibitive cost of full\-length RL \(ℂ​3\\mathbb\{C\}3\)\.

Our experiments show that StateTree substantially improves Qwen2\.5\-7B\-Instruct, Qwen2\.5\-14B\-Instruct and Qwen3\-8B on long\-term dialogue reasoning\. StateTree\-14B achieves an average accuracy of 60\.91% on LoCoMo,surpassing much larger baselinesincluding QwenLong\-L1\-32B\.Trained on contexts of 10K tokens, StateTree models generalize to long\-term conversation reasoning on much longer 128K benchmarks \(LongMemEval, PersonaMem\-128k\), and StateTree preserves short\-context reasoning abilities\.Notably, a qualitative comparison reveals that StateTree\-trained models exhibit four emergent reasoning behaviors \(cross\-session retrieval, temporal reasoning, knowledge update, and multi\-hop composition\) that directly align with the four challenges encoded in the StateTree design, confirming that the synthetic task successfully imparts targeted reasoning patterns that generalize beyond the training distribution\. Our main contributions are:

- •We propose StateTree, a data\-driven RL pseudo\-task that augments scarce multi\-session dialogues with tree\-structured key\-value records, transforming limited data into challenging training instances with verifiable ground truth to enhance long\-term dialogue reasoning\.
- •We develop a curriculum RL strategy that progressively increases tree depth and introduces a compositional variant with step\-level semantic fragments, enabling stable training and eliciting targeted reasoning behaviors\.
- •StateTree elicits emergent reasoning behaviors correspond to its task design\. Despite training on only 616 examples at 10K tokens, it generalizes to 128K contexts without full\-length RL costs, preserves short\-context abilities, and matches or exceeds the performance of much larger models\.

## 2Related Work

Evaluating Long\-term Multi\-Session Dialogues\.As LLMs are increasingly deployed as personalized assistants, understanding their ability to reason over extended interaction histories has become critical\. A key finding is that models exhibit a “lost\-in\-the\-middle” effect, with greater difficulty recalling information in the middle of the context\([Liu et al\., 2024b](https://arxiv.org/html/2609.38809#bib.bib22)\)\.[Laban et al\. \(2026\)](https://arxiv.org/html/2609.38809#bib.bib17)further show that when LLMs take a wrong turn in multi\-turn dialogue, they fail to recover\. Recently, evaluation has shifted toward more realistic dialogue interactions with sessions ranging from 10K to over 100K tokens\. Representative benchmarks include LoCoMo[Maharana et al\. \(2024\)](https://arxiv.org/html/2609.38809#bib.bib12), LongMemEval[Wu et al\. \(2025\)](https://arxiv.org/html/2609.38809#bib.bib11), and PersonaMem[Jiang et al\. \(2025\)](https://arxiv.org/html/2609.38809#bib.bib23)\. These evaluations reveal that even strong models struggle with long\-term dialogue reasoning, motivating two lines of work: memory\-augmented systems[Xu et al\. \(2026\)](https://arxiv.org/html/2609.38809#bib.bib43)and long\-context reasoning methods\.

Long\-Context Reasoning\.Memory\-augmented systems[Zhong et al\. \(2024\)](https://arxiv.org/html/2609.38809#bib.bib1);[Fang et al\. \(2026\)](https://arxiv.org/html/2609.38809#bib.bib2)externalize memory through compression, indexing, and retrieval, but ultimately depend on the backbone LLM’s ability to reason over retrieved context\. Advanced long\-context reasoning primarily utilizes synthetic\-data SFT\([Li et al\., 2024a](https://arxiv.org/html/2609.38809#bib.bib21);[Li et al\., 2024b](https://arxiv.org/html/2609.38809#bib.bib37)\)and RL\([Guo et al\., 2025](https://arxiv.org/html/2609.38809#bib.bib34)\), both of which are constrained by the biases of static synthetic traces or the base model’s intrinsic reasoning capacity\. For example,[Li et al\. \(2024a\)](https://arxiv.org/html/2609.38809#bib.bib21)proposes SEALONG, a self\-improvement approach that samples multiple reasoning outputs and selects high\-quality traces for SFT or preference alignment\. QwenLong\-L1\([Wan et al\., 2025](https://arxiv.org/html/2609.38809#bib.bib14)\)applies RL to extend long reasoning trajectories up to 60K tokens\. Inspired by needle\-in\-a\-haystack\([Kamradt, 2023](https://arxiv.org/html/2609.38809#bib.bib32)\), which measures models’ retrieval ability in extremely long\-text settings, LoongRL[Wang et al\. \(2026\)](https://arxiv.org/html/2609.38809#bib.bib13)inserts chains that hide the true question among distracting documents to support advanced long\-context reasoning\. While these approaches enhance long\-context reasoning, they are designed for static documents rather than the non\-stationary, multi\-session dialogue setting\.

## 3StateTree

![Refer to caption](https://arxiv.org/html/2609.38809v1/question_example.png)Figure 2:Examples of the challenges in multi\-turn dialogue\. For each example, we show the associated evidence statements on the left and the question with the answer on the right\.As shown in Figure[2](https://arxiv.org/html/2609.38809#S3.F2), long\-term interaction dialogues pose four challenges: \(i\)*Cross\-Session Retrieval*,which requires precisely locating sparse, relevant evidence scattered across numerous sessions\([Maharana et al\., 2024](https://arxiv.org/html/2609.38809#bib.bib12)\); \(ii\)*Multi\-Hop Reasoning*,necessitating bridging multiple retrieval steps across sessions and synthesizing the aggregated fragments into a final answer\([Maharana et al\., 2024](https://arxiv.org/html/2609.38809#bib.bib12);[Wu et al\., 2025](https://arxiv.org/html/2609.38809#bib.bib11)\); \(iii\)*Temporal Reasoning*,which involves comparing timestamps across sessions to ground events in chronology\([Wu et al\., 2025](https://arxiv.org/html/2609.38809#bib.bib11)\); and \(iv\)*Knowledge Update*,which requires recognizing that the same topic may be discussed at different times and that the most recent information should take precedence\([Dean and Morgenstern, 2022](https://arxiv.org/html/2609.38809#bib.bib10)\)\.

To overcome these challenges, we propose StateTree, adata\-driven RL pseudo\-task that constructs challenging synthetic auxiliary tasks embedded within authentic dialogues, targeting the capabilities required for long\-term dialogue understanding and providing verifiable ground truth\(see Figure[3](https://arxiv.org/html/2609.38809#S3.F3)\)\. It combines \(i\) a data construction pipeline \(Section[3\.1](https://arxiv.org/html/2609.38809#S3.SS1)\) for challenging task generation; and \(ii\) GRPO with structured curriculum RL training for progressive skill acquisition through increasing tree depth and reasoning complexity, together with a combined reward function using exact match reward to provide clear optimization signals that directly target answer correctness \(Section[3\.2](https://arxiv.org/html/2609.38809#S3.SS2)\)\. These pillars collectively provide a manageable learning path for stable, data\-efficient LLM training\. Table[1](https://arxiv.org/html/2609.38809#S3.T1)summarizes how each challenge is addressed by a specific design choice in StateTree\.

### 3\.1Data Construction Pipeline

The core challenge in training LLMs for long\-term dialogue reasoning is the absence of tasks that demand multi\-step reasoning over extended dialogue histories\. To address this, we design adata\-driven RL pseudo\-taskwith a data construction pipeline that embeds enhanced reasoning challenges directly within authentic multi\-session dialogue data\.

![Refer to caption](https://arxiv.org/html/2609.38809v1/data_construction.png)Figure 3:The StateTree data construction pipeline\.Left:Basic StateTree embeds key\-value records across sessions into a tree; the model traverses root\-to\-leaf to recover the target question\.Right:Compositional StateTree augments edges with step\-level fragments aggregates into the final question\.Table 1:Mapping between multi\-turn dialogue challenges and StateTree design choices\.ChallengeDesign in StateTreeCross\-Session RetrievalEdge records distributed evenly acrossSSsessions, preventing positional shortcutsMulti\-Hop ReasoningDD\-level tree traversal; compositional StateTree requires aggregating step fragments into the questionTemporal ReasoningAt each fork, compare session timestamps to determine chronological orderingKnowledge UpdateCorrect edge is placed in a newer session than the distractor, mirroring real recency preference

Base Data\.We build upon multi\-session dialogue datasets \(e\.g\., LoCoMo[Maharana et al\. \(2024\)](https://arxiv.org/html/2609.38809#bib.bib12)\) where each sample consists of multiple dialogue sessions between two speakers, each annotated with a timestamp\. Each sample is paired with factual QA pairs whose answers can be derived from the dialogue content\.

Task Overview\.The core of our data construction is*StateTree*, a complete binary tree of depthDDbuilt around a target question\-answer pair\(qi,ai\)\(q\_\{i\},a\_\{i\}\)\. The target questionqiq\_\{i\}is hidden in one leaf node, while all edges are encoded as JSON key\-value records scattered across dialogue sessions\. Solving the task requires traversing from root to leaf to recover the hidden question and produceaia\_\{i\}\.

Consider a multi\-session dialogue𝒮=\{s1,…,sS\}\\mathcal\{S\}=\\\{s\_\{1\},\\ldots,s\_\{S\}\\\}, where each session is annotated with a timestamp, paired with a set of questions𝒬\\mathcal\{Q\}and their ground\-truth answers\. For a target questionqi∈𝒬q\_\{i\}\\in\\mathcal\{Q\}with answeraia\_\{i\}, we construct a StateTree𝒯\\mathcal\{T\}and embed its edges as JSON records throughout the sessions, yielding an augmented dialogue𝒮′\\mathcal\{S\}^\{\\prime\}\. Each training instance is then a tuple\(𝒮′,𝒫,ai\)\(\\mathcal\{S\}^\{\\prime\},\\mathcal\{P\},a\_\{i\}\): the model receives𝒮′\\mathcal\{S\}^\{\\prime\}together with an instruction prompt𝒫\\mathcal\{P\}specifying the root keykrootk\_\{\\text\{root\}\}and traversal rules, and must findqiq\_\{i\}and produceaia\_\{i\}\. The design follows three principles, each targeting a specific challenge:\(i\)the original questionqiq\_\{i\}is*hidden*and edge records are distributed across allSSsessions, so the model must perform*cross\-session retrieval*to locate them;\(ii\)at each fork, the correct edge record resides in a*more recent session*than the distractor, forcing*temporal reasoning*and*knowledge update*;\(iii\)the model must navigateDDlevels of forks to reach the leaf, then answer the recovered question, exercising*multi\-hop reasoning*\. We employ two tree formats: a*Basic StateTree*whose leaves directly contain questions, and a*Compositional StateTree*whose edges carry step\-level reasoning fragments that must be aggregated to recover the question\.

Algorithm 1Basic StateTree Construction\.0:

𝒮=\{s1,…,sS\}\\mathcal\{S\}=\\\{s\_\{1\},\\dots,s\_\{S\}\\\}, QA pairs

𝒬\\mathcal\{Q\}, depth

DD
0:​Augmented dialogue

𝒮′\\mathcal\{S\}^\{\\prime\}\\\!, prompt

𝒫\\mathcal\{P\}\\\!, answer

aia\_\{i\}\\\!
1:

\(qi,ai\)∼𝒬\(q\_\{i\},a\_\{i\}\)\\sim\\mathcal\{Q\}
2:Build

𝒯\\mathcal\{T\}\(depth

DD, internal nodes

VintV\_\{\\text\{int\}\}, leaves

LL\); assign UUID key

kvk\_\{v\}to each node

3:Sample

ℓ∗∈L\\ell^\{\*\}\\in L; set

qℓ∗←qiq\_\{\\ell^\{\*\}\}\\leftarrow q\_\{i\}and

qℓ∼𝒬∖\{qi\}q\_\{\\ell\}\\sim\\mathcal\{Q\}\\setminus\\\{q\_\{i\}\\\}for

ℓ≠ℓ∗\\ell\\neq\\ell^\{\*\}
4:foreach

v∈Vintv\\in V\_\{\\text\{int\}\}with children

u1,u2u\_\{1\},u\_\{2\}do

5:for

j∈\{1,2\}j\\in\\\{1,2\\\}do

6:if

uj∈Vintu\_\{j\}\\in V\_\{\\text\{int\}\}then

7:

rj←\{kv:kuj\}r\_\{j\}\\leftarrow\\\{k\_\{v\}:k\_\{u\_\{j\}\}\\\}
8:else

9:

rj←\{kv:quj\}r\_\{j\}\\leftarrow\\\{k\_\{v\}:q\_\{u\_\{j\}\}\\\}
10:endif

11:endfor

12:if

vvon root\-to\-

ℓ∗\\ell^\{\*\}paththen

13:

ucorr←u\_\{\\text\{corr\}\}\\leftarrowon\-path child,

udist←u\_\{\\text\{dist\}\}\\leftarrowsibling

14:Pick

sa,sb∈𝒮s\_\{a\},s\_\{b\}\\in\\mathcal\{S\}with

timestamp​\(sb\)\>timestamp​\(sa\)\\text\{timestamp\}\(s\_\{b\}\)\>\\text\{timestamp\}\(s\_\{a\}\)
15:Assign

rcorrr\_\{\\text\{corr\}\}to

sbs\_\{b\}and

rdistr\_\{\\text\{dist\}\}to

sas\_\{a\}
16:else

17:Assign

r1,r2r\_\{1\},r\_\{2\}to distinct sessions evenly

18:endif

19:endfor

20:Insert all records at sentence boundaries

→𝒮′\\to\\mathcal\{S\}^\{\\prime\}
21:

𝒫←Prompt​\(kroot,traversal rules\)\\mathcal\{P\}\\leftarrow\\textsc\{Prompt\}\(k\_\{\\text\{root\}\},\\text\{traversal rules\}\);

22:return

\(𝒮′,𝒫,ai\)\(\\mathcal\{S\}^\{\\prime\},\\mathcal\{P\},a\_\{i\}\)

Algorithm 2Compositional StateTree Construction\.0:

𝒮=\{s1,…,sS\}\\mathcal\{S\}=\\\{s\_\{1\},\\dots,s\_\{S\}\\\}, target

\(qi,ai\)\(q\_\{i\},a\_\{i\}\), depth

DD, axes

\{A1,…,AD\}\\\{A\_\{1\},\\dots,A\_\{D\}\\\}
0:​Augmented dialogue

𝒮′\\mathcal\{S\}^\{\\prime\}\\\!, prompt

𝒫\\mathcal\{P\}\\\!, answer

aia\_\{i\}\\\!
1:Build

𝒯\\mathcal\{T\}\(depth

DD, keys

kvk\_\{v\}\); sample target leaf

ℓ∗\\ell^\{\*\}
2:Decompose

qiq\_\{i\}via LLM along axes, yielding target step

z\(v,u\)z\_\{\(v,u\)\}for each edge on the root\-to\-

ℓ∗\\ell^\{\*\}path

3:Generate distractor steps for all other root\-to\-leaf paths via LLM, differing in

≥1\\geq 1axis

4:foreach internal node

vvwith children

u1,u2u\_\{1\},u\_\{2\}do

5:for

j∈\{1,2\}j\\in\\\{1,2\\\}do

6:if

uj∉Lu\_\{j\}\\notin Lthen

7:

rj←\{kv:\{step:z\(v,uj\),next:kuj\}\}r\_\{j\}\\\!\\leftarrow\\\!\\\{k\_\{v\}\\\!:\\\!\\\{\\texttt\{step\}:z\_\{\(v,u\_\{j\}\)\},\\texttt\{next\}:k\_\{u\_\{j\}\}\\\}\\\}
8:else

9:

rj←\{kv:\{step:z\(v,uj\)\}\}r\_\{j\}\\leftarrow\\\{k\_\{v\}:\\\{\\texttt\{step\}:z\_\{\(v,u\_\{j\}\)\}\\\}\\\}
10:endif

11:endfor

12:if

vvon root\-to\-

ℓ∗\\ell^\{\*\}paththen

13:

ucorr←u\_\{\\text\{corr\}\}\\leftarrowon\-path child,

udist←u\_\{\\text\{dist\}\}\\leftarrowsibling

14:Pick

sa,sb∈𝒮s\_\{a\},s\_\{b\}\\in\\mathcal\{S\}with

timestamp​\(sb\)\>timestamp​\(sa\)\\text\{timestamp\}\(s\_\{b\}\)\>\\text\{timestamp\}\(s\_\{a\}\)
15:Assign

rcorrr\_\{\\text\{corr\}\}to

sbs\_\{b\}and

rdistr\_\{\\text\{dist\}\}to

sas\_\{a\}
16:else

17:Assign

r1,r2r\_\{1\},r\_\{2\}to distinct sessions evenly

18:endif

19:endfor

20:Insert all records at sentence boundaries

→𝒮′\\to\\mathcal\{S\}^\{\\prime\}
21:

𝒫←Prompt​\(kroot,traversal and composition rules\)\\mathcal\{P\}\\\!\\\!\\leftarrow\\\!\\\!\\textsc\{Prompt\}\(k\_\{\\text\{root\}\},\\text\{traversal and composition rules\}\);

22:return

\(𝒮′,𝒫,ai\)\(\\mathcal\{S\}^\{\\prime\},\\mathcal\{P\},a\_\{i\}\)

Basic StateTree\.The Basic StateTree𝒯\\mathcal\{T\}is a complete binary tree of depthDD\. Each node is identified by a unique*key*—a randomly generated UUID string \(e\.g\.,f391e945\-\.\.\.\-9bbcecd4b90d\) carrying no semantic meaning, forcing the model to perform explicit lookup\-and\-follow operations rather than content\-based shortcuts\. Each of the2D−12^\{D\}\-1internal nodes has exactly two outgoing edges, encoded as JSON key\-value records \(e\.g\.,\{‘‘kik\_\{i\}’’: ‘‘kjk\_\{j\}’’\}\)\. The2D2^\{D\}leaf nodes each contain a natural\-language question: exactly one holds the target questionqiq\_\{i\}; the rest hold distractor questions sampled from𝒬∖\{qi\}\\mathcal\{Q\}\\setminus\\\{q\_\{i\}\\\}, ensuring all leaf questions are plausible and answerable from𝒮′\\mathcal\{S\}^\{\\prime\}, so the model cannot bypass tree navigation by simply selecting the most relevant\-sounding question\. There exists a unique correct pathkroot→k2→⋯→kD→qik\_\{\\text\{root\}\}\\to k\_\{2\}\\to\\cdots\\to k\_\{D\}\\to q\_\{i\}from the root to the target leaf\. The tree contains2​\(2D−1\)2\(2^\{D\}\-1\)edge records in total, all scattered across the dialogue sessions\.

For each internal node on the correct path, its correct and distractor edge records are placed in*different*sessions, with the correct record always in the*more recent*one to force the model toperform*temporal discrimination*by comparing session timestamps to identify the most recent record\.All edge records are inserted at sentence boundaries and distributed evenly across sessions to blend naturally into the dialogue flow\. Algorithm[1](https://arxiv.org/html/2609.38809#alg1)formalizes the construction of a Basic StateTree\. The pipeline first builds a complete binary tree and scatters its edges across the dialogue sessions, then generates an instruction prompt that asks the model to traverse the tree and answer the recovered question\. An example instance is provided in Appendix[E](https://arxiv.org/html/2609.38809#A5)\.

Compositional StateTree\.While the Basic StateTree trains cross\-session retrieval, temporal reasoning, and knowledge update, the model never needs to*compose*information gathered along the path, which is a critical aspect of multi\-hop reasoning\. Thus, we introduce the*Compositional StateTree*, aDD\-level binary tree whose edges carry structured*step*information instead of bare key pointers\. Concretely, given the target questionqiq\_\{i\}for a dialogue between two speakers, we use an LLM \(prompt in Appendix[C\.4\.1](https://arxiv.org/html/2609.38809#A3.SS4.SSS1)\) to decomposeqiq\_\{i\}into a2×2×22\\times 2\\times 2hierarchy along three semantic axes, which define the levels of a depth\-33binary tree with 8 leaves\. Each edge carries astepfield that provides a reasoning fragment at the corresponding level:

- •Person selection \(Level 1\):which speaker is relevant to the dialogue, e\.g\., “\[A\] Jon”
- •Event category \(Level 2\):which broad type of activity is involved, e\.g\., “\[B\] expanding his studio’s social media presence”
- •Question specificity \(Level 3\):the precise question detail, e\.g\., “When did \[A\] start \[B\]?”

The LLM generates alternative combinations along each axis for the remaining 7 leaves, producing distractor questions that share partial semantic overlap withqiq\_\{i\}but differ in at least one axis\. Each edge record is encoded as a nested JSON object\{‘‘kik\_\{i\}’’: \{‘‘step’’: ‘‘\.\.\.’’, ‘‘next’’: ‘‘kjk\_\{j\}’’\}\}for internal edges, or\{‘‘kik\_\{i\}’’: \{‘‘step’’: ‘‘\.\.\.’’\}\}for leaf edges \(nonextfield\)\. Algorithm[2](https://arxiv.org/html/2609.38809#alg2)formalizes the construction of a Compositional StateTree, and examples are provided in Appendix[E](https://arxiv.org/html/2609.38809#A5)\.

The model must\(i\)navigate the tree using the same temporal discrimination as the Basic StateTree;\(ii\)accumulate thestepfragments along the correct root\-to\-leaf path; and\(iii\)aggregate them into the final question before answering it based on the dialogue content\.

### 3\.2Long\-Context Multi\-turn Dialogue Reinforcement Learning

We adopt GRPO[Shao et al\. \(2024\)](https://arxiv.org/html/2609.38809#bib.bib30)with curriculum RL training and a combined reward function\.

Curriculum RL Training\.Training directly on high\-depth trees is difficult for LLMs and often leads to instability\. We therefore adopt afour\-stage curriculum that gradually increases task difficulty\.

- •Warmup: Direct Dialogue QA\.We first warm up the model with RL on the original dialogue QA data, establishing basic long\-context comprehension before introducing tree\-structured tasks\.
- •Stage 1: Basic StateTree \(D=2D\{=\}2\)\.We introduce the Basic StateTree at depthD=2D\{=\}2\(4 leaves, 6 edge records scattered across sessions\), requiring the model to perform cross\-session retrieval and temporal discrimination as fundamental skills to reach the target leaf\.
- •Stage 2: Basic StateTree \(D=3D\{=\}3\)\.We increase the depth toD=3D\{=\}3\(8 leaves, 14 edge records\), adding an additional hop that forces the model to strengthen multi\-hop reasoning\.
- •Stage 3: Compositional StateTree \(D=3D\{=\}3\)\.Stage 3 replaces the Basic StateTree with the Compositional StateTree, adding the compositional skill of accumulating step fragments along the correct path and aggregating them into the final question before answering\.

Combined Reward\.Training with a single reward source is suboptimal: exact\-match \(EM\) reward is overly rigid and rejects semantically correct answers that differ in surface form, while LLM\-as\-a\-Judge suffers from scoring inconsistency and higher computational overhead \(see ablation in Table[8](https://arxiv.org/html/2609.38809#S4.T8)\)\.To provide a stable and semantically faithful optimization signal,we assign the rewardrir\_\{i\}via a combined function that integrates rule\-based verification with LLM\-as\-a\-Judge[Wan et al\. \(2025\)](https://arxiv.org/html/2609.38809#bib.bib14)\. We explicitly require the model to output its final answer within`\\boxed\{\.\.\.\}`in the training prompt \(Appendix[D](https://arxiv.org/html/2609.38809#A4)\), ensuring the extraction of an unambiguous answeryansy\_\{\\text\{ans\}\}\.Formally, given questionxx, extracted answeryansy\_\{\\text\{ans\}\}, and ground\-truth answerygoldy\_\{\\text\{gold\}\}, the reward is defined as:

rϕ​\(x,y\)=max⁡\(rEM​\(yans=ygold\),rLLM​\(x,yans,ygold\)\)r\_\{\\phi\}\(x,y\)=\\max\\big\(r\_\{\\text\{EM\}\}\(y\_\{\\text\{ans\}\}=y\_\{\\text\{gold\}\}\),\\;r\_\{\\text\{LLM\}\}\(x,y\_\{\\text\{ans\}\},y\_\{\\text\{gold\}\}\)\\big\)\(1\)whererEM​\(⋅\)r\_\{\\text\{EM\}\}\(\\cdot\)is the indicator function enforcing exact string matching, andrLLM​\(⋅\)∈\{0,1\}r\_\{\\text\{LLM\}\}\(\\cdot\)\\in\\\{0,1\\\}is a binary semantic equivalence score produced by a Qwen2\.5\-1\.5B\-Instruct\([Yang et al\., 2024](https://arxiv.org/html/2609.38809#bib.bib35)\)\. The judge operates at temperature00with prompt templates \(Appendix[D\.6\.1](https://arxiv.org/html/2609.38809#A4.SS6.SSS1)\) to guarantee deterministic outputs\.

## 4Experiments

### 4\.1Experimental Setup

Training Setup\.We run experiments on Qwen2\.5\-7B\-Instruct[Yang et al\. \(2024\)](https://arxiv.org/html/2609.38809#bib.bib35), Qwen2\.5\-14B\-Instruct[Yang et al\. \(2024\)](https://arxiv.org/html/2609.38809#bib.bib35), and Qwen3\-8B[Yang et al\. \(2025\)](https://arxiv.org/html/2609.38809#bib.bib38)\. We use GRPO with group size 8, prompt batch size 64 for 7B and 8B models and 32 for 14B model, learning rate1×10−61\\times 10^\{\-6\}, gradient clipping 1\.0, and KL penaltyβ=0\.001\\beta\{=\}0\.001\. Rollouts are sampled with temperature 0\.6 and top\-p==0\.95, with a maximum output length of 4,096 tokens\. The curriculum consists of four stages: warm\-up \(40 steps\), Stage 1 \(100 steps\), Stage 2 \(100 steps\), and Stage 3 \(60 steps\)\. To prevent catastrophic forgetting of general reasoning capabilities, we mix 2,500 samples from the DAPO\-Math dataset[Yu et al\. \(2025\)](https://arxiv.org/html/2609.38809#bib.bib39)into Stage 3\. The warm\-up stage uses the 616 training samples in the original direct QA format without trees; Stage 1–3 augment the same 616 samples with StateTree\. The 770 test samples and 154 validation samples both retain the original direct QA format without any StateTree augmentation\. All models are trained on 32×\\timesH20 GPUs\.

Evaluation Benchmarks\.We evaluate models across two dimensions\. \(i\) Long\-term conversation reasoning\.We use LoCoMo[Maharana et al\. \(2024\)](https://arxiv.org/html/2609.38809#bib.bib12)as the in\-domain \(ID\) benchmark, and LongMemEval[Wu et al\. \(2025\)](https://arxiv.org/html/2609.38809#bib.bib11)and PersonaMem[Jiang et al\. \(2025\)](https://arxiv.org/html/2609.38809#bib.bib23)as out\-of\-distribution \(OOD\) benchmarks to test generalization across unseen domains and extended contexts \(10K–128K tokens\)\. We follow official protocols: LoCoMo reports LLM\-judged accuracy \(evaluated by GPT\-4o\), token\-level F1, and BLEU\-1; LongMemEval reports LLM\-judged accuracy \(evaluated by GPT\-4o\); PersonaMem reports exact\-match accuracy\.\(ii\) General short\-context reasoning\.To verify that our long\-context RL training does not induce catastrophic forgetting or degrade foundational reasoning, we additionally evaluate on standard short\-context benchmarks: MMLU\([Hendrycks et al\., 2020](https://arxiv.org/html/2609.38809#bib.bib24)\), MATH\-500\([Lightman et al\., 2023](https://arxiv.org/html/2609.38809#bib.bib25)\), and IFEval\([Zhou et al\., 2023](https://arxiv.org/html/2609.38809#bib.bib5)\)\.All evaluations share a unified inference setup, i\.e\., temperature 0\.6,with up to 128K input tokens and 4096 output tokens\.

Baselines\.We compare our StateTree\-trained models against:\(i\)leading frontier models and long\-context reasoning models, including GPT\-4o[Hurst et al\. \(2024\)](https://arxiv.org/html/2609.38809#bib.bib33), QwenLong\-L1\-32B[Wan et al\. \(2025\)](https://arxiv.org/html/2609.38809#bib.bib14), and R1\-Distill\-Qwen\-32B[Guo et al\. \(2025\)](https://arxiv.org/html/2609.38809#bib.bib34);\(ii\)memory\-augmented models that enhance long\-context reasoning, including the SFT\-based method SEALONG[Li et al\. \(2024a\)](https://arxiv.org/html/2609.38809#bib.bib21)and RL\-based methods LoongRL[Wang et al\. \(2026\)](https://arxiv.org/html/2609.38809#bib.bib13)and RL\-MemAgent[Yu et al\. \(2026\)](https://arxiv.org/html/2609.38809#bib.bib31)\.

### 4\.2Main Results

Table 2:Main results on the LoCoMo benchmark across different task dimensions\.ModelMulti HopTemporalOpen DomainSingle HopAverageACCF1BLEUACCF1BLEUACCF1BLEUACCF1BLEUACCF1BLEUGPT\-4o68\.8432\.2523\.1014\.4710\.2510\.4530\.0018\.4716\.8064\.5449\.3440\.1952\.7336\.2029\.47QwenLong\-L1\-32B64\.4929\.5322\.2734\.5924\.3520\.1948\.0029\.4327\.0244\.6830\.3726\.2046\.3628\.9224\.31R1\-Distill\-Qwen\-32B70\.2926\.8017\.4533\.3315\.9812\.3552\.0025\.1920\.9852\.0123\.0418\.0051\.4322\.4016\.93Qwen2\.5\-7B\-Instruct63\.7721\.3415\.2323\.9012\.6710\.5850\.0016\.8814\.0844\.9221\.9617\.7244\.2919\.6015\.56SEALONG\-7B63\.7727\.5020\.6520\.7515\.1611\.7248\.0025\.8023\.5347\.9932\.0128\.3845\.1927\.3223\.24LoongRL\-7B60\.8728\.8419\.5325\.1618\.2515\.0856\.0023\.5619\.6847\.9932\.9228\.4146\.1028\.5523\.50RL\-MemAgent\-7B64\.4930\.6221\.8831\.4516\.3612\.3146\.0026\.2622\.4149\.1432\.7527\.0748\.0328\.5622\.79StateTree\-7B64\.4931\.2025\.3832\.7033\.9729\.3656\.0036\.1132\.3150\.3536\.0032\.1849\.6134\.7330\.39Qwen2\.5\-14B\-Instruct67\.3931\.9824\.0734\.5914\.5311\.1762\.0027\.3123\.8347\.0434\.3230\.1649\.0929\.3624\.74SEALONG\-14B69\.5735\.6425\.6532\.7015\.8512\.9558\.0026\.3722\.0847\.2832\.7328\.7648\.9629\.3624\.50LoongRL\-14B69\.5733\.2025\.8237\.7420\.5323\.2562\.0034\.1431\.1052\.2535\.7630\.2552\.9932\.0528\.07RL\-MemAgent\-14B67\.3931\.9625\.0137\.1114\.5511\.1360\.0033\.0430\.1050\.5934\.6229\.3951\.4329\.9024\.88StateTree\-14B75\.3638\.4027\.9041\.5140\.7233\.5666\.0039\.6537\.1862\.8838\.3733\.2660\.9138\.9432\.62Qwen3\-8B64\.4931\.3222\.1329\.5618\.9115\.3148\.0021\.418\.5543\.0326\.3723\.0243\.6425\.3920\.98StateTree\-8B70\.2936\.0725\.5837\.7431\.7829\.2556\.0036\.3633\.0851\.0636\.7531\.8952\.0835\.5830\.29

Table 3:OOD generalization accuracy \(%\) on LongMemEval and PersonaMem\-128k benchmarks\.LongMemEval \(128k\)PersonaMem \(128k\)ModelTemp\.Multi\-Ses\.Know\.Upd\.SS\-UserSS\-Asst\.SS\-Pref\.Avg\.LatestPref\.NewScen\.Align\.Rec\.SharedFactRevisitReas\.NewIdeaTrackEvol\.Avg\.QwenLong\-L1\-32B47\.3735\.3456\.4180\.0067\.8623\.3351\.0057\.5148\.8347\.5666\.0881\.0425\.4858\.0652\.40R1\-Distill\-Qwen\-32B21\.8013\.5350\.0034\.2957\.1410\.0029\.0033\.0321\.6033\.5236\.8463\.5722\.3966\.5737\.62Qwen2\.5\-7B\-Instruct20\.308\.2752\.5625\.7137\.503\.3323\.8037\.4136\.1545\.5647\.9562\.0815\.6462\.7640\.48SEALONG\-7B28\.5728\.5764\.1075\.7176\.7916\.6745\.4037\.9939\.4446\.9947\.3764\.6816\.8063\.6441\.66LoongRL\-7B24\.065\.2655\.1337\.1442\.863\.3326\.6029\.5623\.0039\.8335\.0941\.2621\.8137\.5431\.39RL\-MemAgent\-7B28\.5717\.2958\.9778\.5776\.7913\.3341\.8043\.0733\.3345\.2749\.1265\.0623\.1762\.4643\.78StateTree\-7B29\.3231\.5867\.9575\.7176\.7923\.3347\.4046\.4239\.9151\.0049\.7168\.0323\.3669\.2147\.30Qwen2\.5\-14B\-Instruct37\.5927\.8267\.9565\.7166\.0710\.0045\.2043\.7638\.0352\.1557\.3168\.0318\.3464\.5245\.40SEALONG\-14B40\.6030\.0867\.9572\.8666\.0713\.3347\.8045\.8438\.9751\.2961\.4068\.7715\.4466\.2846\.02LoongRL\-14B40\.6036\.8469\.2381\.4389\.2923\.3354\.2048\.1540\.8556\.1660\.2368\.7718\.1567\.1648\.07RL\-MemAgent\-14B42\.1129\.3267\.9585\.7182\.1420\.0052\.0047\.6939\.4453\.3060\.8271\.0021\.0466\.2848\.15StateTree\-14B42\.1148\.1270\.5187\.1485\.7136\.6759\.0051\.6246\.4859\.8964\.3377\.3223\.5570\.0952\.59Qwen3\-8B35\.3439\.1066\.6772\.8669\.6416\.6749\.2053\.8139\.4437\.8248\.5469\.5216\.6058\.3645\.36StateTree\-8B41\.0047\.4778\.2185\.4583\.9326\.0958\.6658\.3146\.9541\.2646\.7872\.8621\.0469\.7950\.31

StateTree improves long\-term dialogue reasoning with high data efficiency\.As shown in Table[2](https://arxiv.org/html/2609.38809#S4.T2), StateTree delivers consistent performance gains over both SFT and standard RL baselines across parameter scales and base architectures on LoCoMo\. StateTree\-14B achieves 60\.91% average accuracy, yielding a \+11\.82% absolute improvement over its base model \(Qwen2\.5\-14B\-Instruct\), while maintaining stable relative gains at the 7B scale\. Notably, despite training on only 616 examples, it matches or exceeds the absolute performance of substantially larger models \(e\.g\., surpassing GPT\-4o by 8\.18% and QwenLong\-L1\-32B by 14\.55%\), underscoring its high sample efficiency\. The most pronounced lift occurs in Temporal reasoning \(F1 \+26\.19 for 14B\), which directly stems from the tree structure’s explicit timestamp comparison at each branching step\.

Table 4:Average accuracy \(%\) across context lengths\.ModelLoCoMoPersonaMemLongMemEval10K32K128K128KQwen2\.5\-7B\-Instruct44\.2953\.1440\.4823\.80StateTree\-7B49\.61\+5\.3261\.29\+8\.1547\.30\+6\.8247\.40\+23\.60Qwen2\.5\-14B\-Instruct49\.0958\.9145\.4045\.20StateTree\-14B60\.91\+11\.8264\.52\+5\.6152\.59\+7\.1959\.00\+13\.80Qwen3\-8B43\.6458\.2345\.3649\.20StateTree\-8B52\.08\+8\.4462\.82\+4\.5950\.31\+4\.9558\.66\+9\.46

Robust out\-of\-distribution and length generalization\.To evaluate out\-of\-distribution generalization, we evaluate StateTree on LongMemEval\([Wu et al\., 2025](https://arxiv.org/html/2609.38809#bib.bib11)\)and PersonaMem\-128k\([Jiang et al\., 2025](https://arxiv.org/html/2609.38809#bib.bib23)\)\.Trained exclusively on 10K\-token contexts, StateTree generalizes to unseen benchmarks with up to 128K tokens\.As shown in Table[3](https://arxiv.org/html/2609.38809#S4.T3), StateTree\-14B achieves 59\.00% on LongMemEval and 52\.59% on PersonaMem\-128k, outperforming both base models and strong baselines including QwenLong\-L1\-32B and RL\-MemAgent\-14B\.The widening performance gap at longer contexts \(Table[4](https://arxiv.org/html/2609.38809#S4.T4)\) demonstrates that the learned path\-tracing strategy extrapolates effectively beyond the 10K training horizon, validating our curriculum design as an alternative to prohibitive full\-length RL costs \(ℂ​3\\mathbb\{C\}3\)\.

Table 5:Short\-context reasoning performance \(%\)\.ModelMMLUMATHIFEvalAvg\.Qwen2\.5\-7B\-Instruct73\.476\.071\.273\.5StateTree\-7B73\.5\+0\.1076\.0\+0\.0070\.5\-0\.7073\.3\-0\.20Qwen2\.5\-14B\-Instruct79\.483\.481\.081\.3StateTree\-14B79\.8\+0\.4083\.0\-0\.4079\.3\-1\.7080\.7\-0\.60Qwen3\-8B76\.978\.285\.080\.0StateTree\-8B77\.0\+0\.1078\.1\-0\.1085\.2\+0\.2080\.1\+0\.10

StateTree preserves short\-context abilities without capability trade\-offs\.A common concern with long\-context RL is the degradation of general reasoning\.As shown in Table[5](https://arxiv.org/html/2609.38809#S4.T5), StateTree maintains competitive performance across standard short\-context benchmarks \(MMLU, MATH, IFEval\)\. Notably, the 8B variant exhibits zero degradation, achieving a marginal \+0\.1% average gain over the base Qwen3\-8B, while the 7B and 14B models incur minimal drops of only \-0\.2% and \-0\.6%, respectively\.

### 4\.3Analysis

Multi\-stage curriculum RL training sustains improvements\.As shown in Figure[4](https://arxiv.org/html/2609.38809#S4.F4), the average F1 score on the validation set rises monotonically across training stages, and the average response length steadily increases alongside it, indicating that the model learns to produce detailed reasoning traces as task complexity increases\. The sustained growth in both metrics with no sign of reward hacking confirms that the combined reward provides a stable training signal and that the multi\-stage curriculum effectively scales model reasoning\.

Figure 4:Reasoning F1 score and response lengths throughout RL training on the validation set\.Emergent reasoning behaviors align with task design\.Qualitative analysis \(Figure[1](https://arxiv.org/html/2609.38809#S1.F1)in Section[1](https://arxiv.org/html/2609.38809#S1)and Appendix[K](https://arxiv.org/html/2609.38809#A11)\) reveals four emergent behaviors that directly explain the quantitative gains:\(i\)*Cross\-session retrieval\.*Rather than stopping at the first matching session, StateTree enumerates all relevant records across sessions before aggregating a complete answer\. \(ii\)*Multi\-hop reasoning\.*Rather than identifying isolated facts, StateTree chains multiple retrieval steps and synthesizes scattered evidence into a coherent inference\. \(iii\)*Temporal reasoning\.*Rather than relying on superficial cues such as “recently,” StateTree extracts concrete session timestamps and performs explicit chronological comparison at each fork\. \(iv\)*Knowledge update\.*Rather than conflating old and new mentions, StateTree correctly tracks the latest state by privileging information from more recent sessions\.These behaviors arise from the StateTree pseudo\-task design, confirming that our auxiliary training signal successfully imparts targeted reasoning patterns that can transfer beyond the training distribution\.

### 4\.4Ablation Study

Table 6:Curriculum stage ablation\.VariantLoCoMoLongMemEvalPersonaMemStateTree\-7B \(full\)49\.6147\.4047\.30w/o warm\-up45\.19\-4\.4243\.00\-4\.4044\.00\-3\.30w/o Stage 1 \(D=2D\{=\}2\)44\.68\-4\.9342\.60\-4\.8043\.78\-3\.52w/o Stage 2 \(D=3D\{=\}3\)46\.23\-3\.3844\.20\-3\.2045\.10\-2\.20w/o Stage 3 \(Compositional\)46\.75\-2\.8644\.80\-2\.6045\.51\-1\.79

Every curriculum stage contributes\.Table[6](https://arxiv.org/html/2609.38809#S4.T6)ablates each stage individually, where the omitted stage is skipped and the remaining stages retain their original step allocations\. Removing Stage 1 \(D=2D\{=\}2\) causes the largest drop \(\-4\.93\), confirming that shallow tree navigation is the most critical foundational skill\. Removing warm\-up follows \(−4\.42\-4\.42\), showing that grounding in basic conversation QA is essential before tree tasks\. Removing Stage 2 \(D=3D\{=\}3\) and Stage 3 \(Compositional\) degrade performance by \-3\.38 and \-2\.86, respectively, indicating their roles in strengthening multi\-hop temporal reasoning and enabling compositional reasoning\. Appendix[H](https://arxiv.org/html/2609.38809#A8)provides a per\-category breakdown that further corroborates the curriculum design\.This sustained uplift validates our staged design: by progressively introducing foundational comprehension, temporal discrimination, and compositional reasoning, the curriculum enables stable skill accumulation without catastrophic forgetting, effectively distilling transferable long\-context primitives from a compact training set\.

Table 7:Temporal discrimination ablation\.VariantLoCoMoLongMemEvalPersonaMemQwen2\.5\-7B\-Instruct44\.2923\.8040\.48w/ CoT prompt45\.19\+0\.9024\.60\+0\.8041\.11\+0\.63StateTree\-7B49\.6147\.4047\.30w/Independent Random Keys45\.45\-4\.1625\.20\-22\.2041\.03\-6\.27w/ Single Session47\.79\-1\.8242\.80\-4\.6043\.96\-3\.34w/ Entity Keys48\.44\-1\.1745\.60\-1\.8045\.98\-1\.32

Task structure drives the training signal\.To confirm that StateTree’s efficacy stems from the synergistic integration of key\-paired forks, cross\-session scattering, and identifier opacity—rather than from merely inserting structured records or prompting longer reasoning, we designfour variants to isolate the contribution of each structural design choice \(Table[7](https://arxiv.org/html/2609.38809#S4.T7)\)\.

- •*w/ CoT prompt*:While Figure[4](https://arxiv.org/html/2609.38809#S4.F4)shows that StateTree training naturally elicits progressively longer reasoning traces, prompting the base model via a modified system prompt \(Appendix[D\.5](https://arxiv.org/html/2609.38809#A4.SS5)\) that instructs it to “think step by step” yields only marginal gains\. This confirms that generic CoT cannot substitute for explicit structural navigation\. The core bottleneck lies in unstructured cross\-session retrieval and temporal discrimination, not insufficient reasoning depth\.
- •*w/ Independent Random Keys*: assigning independent random keys to each fork’s competing edge records eliminates shared identifiers,preventing the model from locating competing records or performing temporal comparison\.The resulting performance demonstrates that StateTree’s gains originate specifically from the shared\-key mechanism enabling explicit fork resolution, rather than from merely injecting records or arbitrary syntactic noise during RL training\.
- •*w/ Single Session*: preserving key pairing but placing all records within one session eliminates cross\-session retrieval\.The intermediate performance confirms that cross\-session distribution and temporal discrimination provide complementary, non\-redundant learning signals\.
- •*w/ Entity Keys*: replacing random UUIDs with common words from a word pool \(Appendix[C\.7](https://arxiv.org/html/2609.38809#A3.SS7)\) captures 80% of the full gain\.The remaining deficit reveals that semantically interpretable keys invite shallow lexical shortcuts, whereas opaque identifiers force genuine temporal reasoning\.

Table 8:Reward function ablation\.RewardLoCoMoLongMemEvalPersonaMemCombined Reward49\.6147\.4047\.30Exact Match only47\.79\-1\.8246\.80\-0\.6046\.68\-0\.62LLM\-as\-a\-Judge only48\.70\-0\.9146\.60\-0\.8046\.75\-0\.55Token\-level F147\.14\-2\.4745\.00\-2\.4045\.29\-2\.01Two\-way Substr\. EM44\.68\-4\.9342\.40\-5\.0043\.31\-3\.99ROUGE\-L42\.60\-7\.0139\.40\-8\.0041\.29\-6\.01

Combined reward is critical forstable optimization\.Table[8](https://arxiv.org/html/2609.38809#S4.T8)compares reward designs under identical training settings\. The combined reward balances strict correctness with semantic flexibility\. EM alone rejects valid paraphrases due to surface\-form rigidity, while standalone LLM\-Judge suffers from scoring inconsistency and higher compute overhead\. Dense lexical metrics \(Token F1, Substring EM\) and ROUGE\-L underperform by rewarding incorrect partial matches or superficial n\-gram overlap\. Thus, the max\-selection mechanism is essential to provide a dense yet reliable training signal aligned with answer correctness\.

## 5Conclusion

We present StateTree, a data\-driven RL pseudo\-task thatreframes long\-term dialogue reasoning as a temporally constrained path\-search problem\. By embedding tree\-structured auxiliary tasks into authentic multi\-session dialogues and optimizing them via a structured curriculum with combined\-reward GRPO, StateTree elicits cross\-session retrieval, temporal reasoning, knowledge update, and compositional multi\-hop reasoning from only 616 examples at 10K context\.Empirically, it yields substantial gains across both in\-domain and out\-of\-domain benchmarks, even surpassing larger baselines\.Crucially, the trained models generalize from 10K to 128K contexts without degrading short\-context capabilities and exhibit emergent reasoning behaviors aligned with the StateTree design\. StateTree establishes a scalable, data\-efficient paradigm for long\-term dialogue reasoning\.

## Acknowledgments

This work was partly supported by the NSFC under No\. 62402418, the “Pioneer and Leading Goose” R&D Program of Zhejiang under No\. 2026C02A1233 and 2025C02034, the Key R&D Program of Ningbo under No\. 2024Z115, and the Ningbo Yongjiang Talent Project\.

## References

- \[1\]S\. Mysore, Z\. Lu, M\. Wan, L\. Yang, B\. Sarrafzadeh, S\. Menezes, T\. Baghaee, E\. B\. Gonzalez, J\. Neville, and T\. Safavi\(2024\)Pearl: personalizing large language model writing assistants with generation\-calibrated retrievers\.InProceedings of the 1st Workshop on Customizable NLP: Progress and Challenges in Customizing NLP for a Domain, Application, Group, or Individual \(CustomNLP4U\),S\. Kumar, V\. Balachandran, C\. Y\. Park, W\. Shi, S\. A\. Hayati, Y\. Tsvetkov, N\. Smith, H\. Hajishirzi, D\. Kang, and D\. Jurgens \(Eds\.\),Miami, Florida, USA,pp\. 198–219\.External Links:[Link](https://aclanthology.org/2024.customnlp4u-1.16/),[Document](https://dx.doi.org/10.18653/v1/2024.customnlp4u-1.16)Cited by:[§1](https://arxiv.org/html/2609.38809#S1.p1.1)\.
- \[2\]Y\. Tian, T\. Huang, M\. Liu, D\. Jiang, A\. Spangher, M\. Chen, J\. May, and N\. Peng\(2024\)Are large language models capable of generating human\-level narratives?\.InProceedings of the 2024 Conference on Empirical Methods in Natural Language Processing,Y\. Al\-Onaizan, M\. Bansal, and Y\. Chen \(Eds\.\),Miami, Florida, USA,pp\. 17659–17681\.External Links:[Link](https://aclanthology.org/2024.emnlp-main.978/),[Document](https://dx.doi.org/10.18653/v1/2024.emnlp-main.978)Cited by:[§1](https://arxiv.org/html/2609.38809#S1.p1.1)\.
- \[3\]W\. Hua, L\. Li, S\. Xu, L\. Chen, and Y\. Zhang\(2023\)Tutorial on large language models for recommendation\.InProceedings of the 17th ACM Conference on Recommender Systems,pp\. 1281–1283\.Cited by:[§1](https://arxiv.org/html/2609.38809#S1.p1.1)\.
- \[4\]Y\. Li, Y\. Zhang, W\. Liu, X\. Feng, Z\. Han, C\. Chen, and C\. Yan\(2025\)Multi\-objective unlearning in recommender systems via preference guided pareto exploration\.IEEE Transactions on Services Computing\.Cited by:[§1](https://arxiv.org/html/2609.38809#S1.p1.1)\.
- \[5\]Y\. Li, X\. Feng, C\. Chen, and Q\. Yang\(2025\)A Survey on Recommendation Unlearning: Fundamentals, Taxonomy, Evaluation, and Open Questions\.IEEE Transactions on Knowledge & Data Engineering\(01\),pp\. 1–20\.External Links:ISSN 1558\-2191,[Document](https://dx.doi.org/10.1109/TKDE.2025.3638174)Cited by:[§1](https://arxiv.org/html/2609.38809#S1.p1.1)\.
- \[6\]C\. Chen, Y\. Zhang, Y\. Li, J\. Wang, L\. Qi, X\. Xu, X\. Zheng, and J\. Yin\(2024\)Post\-training attribute unlearning in recommender systems\.ACM Transactions on Information Systems43\(1\),pp\. 1–28\.Cited by:[§1](https://arxiv.org/html/2609.38809#S1.p1.1)\.
- \[7\]J\. Xie, K\. Zhang, J\. Chen, T\. Zhu, R\. Lou, Y\. Tian, Y\. Xiao, and Y\. Su\(2024\)TravelPlanner: a benchmark for real\-world planning with language agents\.InProceedings of the 41st International Conference on Machine Learning,pp\. 54590–54613\.Cited by:[§1](https://arxiv.org/html/2609.38809#S1.p1.1)\.
- \[8\]Y\. Du, B\. Wang, Y\. He, B\. Liang, B\. Wang, Z\. Li, L\. Gui, J\. Z\. Pan, R\. Xu, and K\. Wong\(2025\)Bridging the long\-term gap: a memory\-active policy for multi\-session task\-oriented dialogue\.arXiv e\-prints,pp\. arXiv–2505\.Cited by:[§1](https://arxiv.org/html/2609.38809#S1.p1.1)\.
- \[9\]W\. Zhong, L\. Guo, Q\. Gao, H\. Ye, and Y\. Wang\(2024\)Memorybank: enhancing large language models with long\-term memory\.InProceedings of the AAAI conference on artificial intelligence,Vol\.38,pp\. 19724–19731\.Cited by:[§1](https://arxiv.org/html/2609.38809#S1.p1.1),[§2](https://arxiv.org/html/2609.38809#S2.p2.1)\.
- \[10\]P\. Laban, H\. Hayashi, Y\. Zhou, and J\. Neville\(2026\)LLMs get lost in multi\-turn conversation\.InThe Fourteenth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=VKGTGGcwl6)Cited by:[§1](https://arxiv.org/html/2609.38809#S1.p1.1),[§2](https://arxiv.org/html/2609.38809#S2.p1.1)\.
- \[11\]Z\. Ling, K\. Liu, K\. Yan, Y\. Yang, W\. Lin, T\. Fan, L\. Shen, Z\. Du, and J\. Chen\(2025\)Longreason: a synthetic long\-context reasoning benchmark via context expansion\.arXiv preprint arXiv:2501\.15089\.Cited by:[§1](https://arxiv.org/html/2609.38809#S1.p1.1)\.
- \[12\]J\. Fang, X\. Deng, H\. Xu, Z\. Jiang, Y\. Tang, Z\. Xu, S\. Deng, Y\. Yao, M\. Wang, S\. Qiao, H\. Chen, and N\. Zhang\(2026\)LightMem: lightweight and efficient memory\-augmented generation\.InThe Fourteenth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=dyJ0GWpjJB)Cited by:[§1](https://arxiv.org/html/2609.38809#S1.p1.1),[§2](https://arxiv.org/html/2609.38809#S2.p2.1)\.
- \[13\]Z\. Yang, P\. Qi, S\. Zhang, Y\. Bengio, W\. Cohen, R\. Salakhutdinov, and C\. D\. Manning\(2018\)HotpotQA: a dataset for diverse, explainable multi\-hop question answering\.InProceedings of the 2018 conference on empirical methods in natural language processing,pp\. 2369–2380\.Cited by:[§1](https://arxiv.org/html/2609.38809#S1.p1.1)\.
- \[14\]X\. Ho, A\. D\. Nguyen, S\. Sugawara, and A\. Aizawa\(2020\)Constructing a multi\-hop qa dataset for comprehensive evaluation of reasoning steps\.InProceedings of the 28th International Conference on Computational Linguistics,pp\. 6609–6625\.Cited by:[§1](https://arxiv.org/html/2609.38809#S1.p1.1)\.
- \[15\]A\. Maharana, D\. Lee, S\. Tulyakov, M\. Bansal, F\. Barbieri, and Y\. Fang\(2024\)Evaluating very long\-term conversational memory of llm agents\.InProceedings of the 62nd Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\),pp\. 13851–13870\.Cited by:[§B\.1](https://arxiv.org/html/2609.38809#A2.SS1.p1.1),[§C\.1](https://arxiv.org/html/2609.38809#A3.SS1.p1.1),[§D\.2](https://arxiv.org/html/2609.38809#A4.SS2.p1.1),[1st item](https://arxiv.org/html/2609.38809#A7.I1.i1.p1.1),[1st item](https://arxiv.org/html/2609.38809#S1.I1.i1.p1.1),[§1](https://arxiv.org/html/2609.38809#S1.p1.1),[§2](https://arxiv.org/html/2609.38809#S2.p1.1),[§3\.1](https://arxiv.org/html/2609.38809#S3.SS1.p2.1),[§3](https://arxiv.org/html/2609.38809#S3.p1.1),[§4\.1](https://arxiv.org/html/2609.38809#S4.SS1.p2.1.2)\.
- \[16\]D\. Wu, H\. Wang, W\. Yu, Y\. Zhang, K\. Chang, and D\. Yu\(2025\)LongMemEval: benchmarking chat assistants on long\-term interactive memory\.InThe Thirteenth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=pZiyCaVuti)Cited by:[§B\.1](https://arxiv.org/html/2609.38809#A2.SS1.p1.1),[2nd item](https://arxiv.org/html/2609.38809#A7.I1.i2.p1.1),[§1](https://arxiv.org/html/2609.38809#S1.p1.1),[§2](https://arxiv.org/html/2609.38809#S2.p1.1),[§3](https://arxiv.org/html/2609.38809#S3.p1.1),[§4\.1](https://arxiv.org/html/2609.38809#S4.SS1.p2.1.2),[§4\.2](https://arxiv.org/html/2609.38809#S4.SS2.p2.1)\.
- \[17\]A\. Liu, B\. Feng, B\. Xue, B\. Wang, B\. Wu, C\. Lu, C\. Zhao, C\. Deng, C\. Zhang, C\. Ruan,et al\.\(2024\)Deepseek\-v3 technical report\.arXiv preprint arXiv:2412\.19437\.Cited by:[3rd item](https://arxiv.org/html/2609.38809#S1.I1.i3.p1.1)\.
- \[18\]A\. Li, B\. Gong, B\. Yang, B\. Shan, C\. Liu, C\. Zhu, C\. Zhang, C\. Guo, D\. Chen, D\. Li,et al\.\(2025\)Minimax\-01: scaling foundation models with lightning attention\.arXiv preprint arXiv:2501\.08313\.Cited by:[3rd item](https://arxiv.org/html/2609.38809#S1.I1.i3.p1.1)\.
- \[19\]B\. Peng, J\. Quesnelle, H\. Fan, and E\. Shippole\(2023\)Yarn: efficient context window extension of large language models\.arXiv preprint arXiv:2309\.00071\.Cited by:[3rd item](https://arxiv.org/html/2609.38809#S1.I1.i3.p1.1)\.
- \[20\]N\. Shang, L\. L\. Zhang, S\. Wang, G\. Zhang, G\. Lopez, F\. Yang, W\. Chen, and M\. Yang\(2025\)Longrope2: near\-lossless llm context window scaling\.arXiv preprint arXiv:2502\.20082\.Cited by:[3rd item](https://arxiv.org/html/2609.38809#S1.I1.i3.p1.1)\.
- \[21\]A\. Prabhakar, Z\. Liu, M\. Zhu, J\. Zhang, T\. Awalgaonkar, S\. Wang, Z\. Liu, H\. Chen, T\. Hoang, J\. C\. Niebles,et al\.\(2025\)Apigen\-mt: agentic pipeline for multi\-turn data generation via simulated agent\-human interplay\.arXiv preprint arXiv:2504\.03601\.Cited by:[§1](https://arxiv.org/html/2609.38809#S1.p3.1)\.
- \[22\]M\. Liu, S\. Diao, X\. Lu, J\. Hu, X\. Dong, Y\. Choi, J\. Kautz, and Y\. Dong\(2025\)Prorl: prolonged reinforcement learning expands reasoning boundaries in large language models\.arXiv preprint arXiv:2505\.24864\.Cited by:[§1](https://arxiv.org/html/2609.38809#S1.p3.1)\.
- \[23\]T\. Chu, Y\. Zhai, J\. Yang, S\. Tong, S\. Xie, D\. Schuurmans, Q\. V\. Le, S\. Levine, and Y\. Ma\(2025\)Sft memorizes, rl generalizes: a comparative study of foundation model post\-training\.arXiv preprint arXiv:2501\.17161\.Cited by:[§1](https://arxiv.org/html/2609.38809#S1.p3.1)\.
- \[24\]D\. Guo, D\. Yang, H\. Zhang, J\. Song, P\. Wang, Q\. Zhu, R\. Xu, R\. Zhang, S\. Ma, X\. Bi,et al\.\(2025\)Deepseek\-r1: incentivizing reasoning capability in llms via reinforcement learning\.arXiv preprint arXiv:2501\.12948\.Cited by:[§F\.1](https://arxiv.org/html/2609.38809#A6.SS1.p1.3),[§1](https://arxiv.org/html/2609.38809#S1.p3.1),[§2](https://arxiv.org/html/2609.38809#S2.p2.1),[§4\.1](https://arxiv.org/html/2609.38809#S4.SS1.p3.1.5)\.
- \[25\]Z\. Shao, P\. Wang, Q\. Zhu, R\. Xu, J\. Song, X\. Bi, H\. Zhang, M\. Zhang, Y\. Li, Y\. Wu,et al\.\(2024\)Deepseekmath: pushing the limits of mathematical reasoning in open language models\.arXiv preprint arXiv:2402\.03300\.Cited by:[§1](https://arxiv.org/html/2609.38809#S1.p3.1),[§3\.2](https://arxiv.org/html/2609.38809#S3.SS2.p1.1)\.
- \[26\]N\. F\. Liu, K\. Lin, J\. Hewitt, A\. Paranjape, M\. Bevilacqua, F\. Petroni, and P\. Liang\(2024\)Lost in the middle: how language models use long contexts\.Transactions of the Association for Computational Linguistics12,pp\. 157–173\.Cited by:[§2](https://arxiv.org/html/2609.38809#S2.p1.1)\.
- \[27\]B\. Jiang, Z\. Hao, Y\. Cho, B\. Li, Y\. Yuan, S\. Chen, L\. Ungar, C\. J\. Taylor, and D\. Roth\(2025\)Know me, respond to me: benchmarking llms for dynamic user profiling and personalized responses at scale\.arXiv preprint arXiv:2504\.14225\.Cited by:[6th item](https://arxiv.org/html/2609.38809#A7.I1.i6.p1.1),[§2](https://arxiv.org/html/2609.38809#S2.p1.1),[§4\.1](https://arxiv.org/html/2609.38809#S4.SS1.p2.1.2),[§4\.2](https://arxiv.org/html/2609.38809#S4.SS2.p2.1)\.
- \[28\]N\. Xu, H\. An, S\. Shi, J\. Zhang, C\. Zhou, C\. Li, T\. Du, Z\. Fu, J\. Wang, and S\. Ji\(2026\)When agents “misremember” collectively: exploring the mandela effect in LLM\-based multi\-agent systems\.InThe Fourteenth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=yIoMqDes7O)Cited by:[§2](https://arxiv.org/html/2609.38809#S2.p1.1)\.
- \[29\]S\. Li, C\. Yang, Z\. Cheng, L\. Liu, M\. Yu, Y\. Yang, and W\. Lam\(2024\)Large language models can self\-improve in long\-context reasoning\.arXiv preprint arXiv:2411\.08147\.Cited by:[1st item](https://arxiv.org/html/2609.38809#A9.I1.i1.p1.1),[§2](https://arxiv.org/html/2609.38809#S2.p2.1),[§4\.1](https://arxiv.org/html/2609.38809#S4.SS1.p3.1)\.
- \[30\]Y\. Li, S\. Liang, M\. Lyu, and L\. Wang\(2024\)Making long\-context language models better multi\-hop reasoners\.InProceedings of the 62nd Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\),pp\. 2462–2475\.Cited by:[§2](https://arxiv.org/html/2609.38809#S2.p2.1)\.
- \[31\]F\. Wan, W\. Shen, S\. Liao, Y\. Shi, C\. Li, Z\. Yang, J\. Zhang, F\. Huang, J\. Zhou, and M\. Yan\(2025\)Qwenlong\-l1: towards long\-context large reasoning models with reinforcement learning\.arXiv preprint arXiv:2505\.17667\.Cited by:[§2](https://arxiv.org/html/2609.38809#S2.p2.1),[§3\.2](https://arxiv.org/html/2609.38809#S3.SS2.p3.1.4),[§4\.1](https://arxiv.org/html/2609.38809#S4.SS1.p3.1.4)\.
- \[32\]G\. Kamradt\(2023\)Needle in a haystack \- pressure testing llms\.External Links:[Link](https://github.com/gkamradt/LLMTest_NeedleInAHaystack)Cited by:[§2](https://arxiv.org/html/2609.38809#S2.p2.1)\.
- \[33\]S\. Wang, G\. Zhang, L\. L\. Zhang, N\. Shang, F\. Yang, D\. Chen, and M\. Yang\(2026\)LoongRL: reinforcement learning for advanced reasoning over long contexts\.InThe Fourteenth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=o29E01Q6bv)Cited by:[3rd item](https://arxiv.org/html/2609.38809#A9.I1.i3.p1.1),[§2](https://arxiv.org/html/2609.38809#S2.p2.1),[§4\.1](https://arxiv.org/html/2609.38809#S4.SS1.p3.1)\.
- \[34\]S\. Dean and J\. Morgenstern\(2022\)Preference dynamics under personalized recommendations\.InProceedings of the 23rd ACM Conference on Economics and Computation,pp\. 795–816\.Cited by:[§3](https://arxiv.org/html/2609.38809#S3.p1.1)\.
- \[35\]A\. Yang, B\. Yang, B\. Hui, B\. Zheng, B\. Yu, C\. Zhou, C\. Li, C\. Li, D\. Liu, F\. Huang, G\. Dong, H\. Wei, H\. Lin, J\. Tang, J\. Wang, J\. Yang, J\. Tu, J\. Zhang, J\. Ma, J\. Xu, J\. Zhou, J\. Bai, J\. He, J\. Lin, K\. Dang, K\. Lu, K\. Chen, K\. Yang, M\. Li, M\. Xue, N\. Ni, P\. Zhang, P\. Wang, R\. Peng, R\. Men, R\. Gao, R\. Lin, S\. Wang, S\. Bai, S\. Tan, T\. Zhu, T\. Li, T\. Liu, W\. Ge, X\. Deng, X\. Zhou, X\. Ren, X\. Zhang, X\. Wei, X\. Ren, Y\. Fan, Y\. Yao, Y\. Zhang, Y\. Wan, Y\. Chu, Y\. Liu, Z\. Cui, Z\. Zhang, and Z\. Fan\(2024\)Qwen2 technical report\.arXiv preprint arXiv:2407\.10671\.Cited by:[§B\.1](https://arxiv.org/html/2609.38809#A2.SS1.p1.1),[§3\.2](https://arxiv.org/html/2609.38809#S3.SS2.p3.2.1),[§4\.1](https://arxiv.org/html/2609.38809#S4.SS1.p1.1)\.
- \[36\]A\. Yang, A\. Li, B\. Yang, B\. Zhang, B\. Hui, B\. Zheng, B\. Yu, C\. Gao, C\. Huang, C\. Lv,et al\.\(2025\)Qwen3 technical report\.arXiv preprint arXiv:2505\.09388\.Cited by:[§4\.1](https://arxiv.org/html/2609.38809#S4.SS1.p1.1)\.
- \[37\]Q\. Yu, Z\. Zhang, R\. Zhu, Y\. Yuan, X\. Zuo, Y\. Yue, W\. Dai, T\. Fan, G\. Liu, L\. Liu,et al\.\(2025\)Dapo: an open\-source llm reinforcement learning system at scale\.arXiv preprint arXiv:2503\.14476\.Cited by:[§4\.1](https://arxiv.org/html/2609.38809#S4.SS1.p1.1)\.
- \[38\]D\. Hendrycks, C\. Burns, S\. Basart, A\. Zou, M\. Mazeika, D\. Song, and J\. Steinhardt\(2020\)Measuring massive multitask language understanding\.arXiv preprint arXiv:2009\.03300\.Cited by:[3rd item](https://arxiv.org/html/2609.38809#A7.I1.i3.p1.1),[§4\.1](https://arxiv.org/html/2609.38809#S4.SS1.p2.1.3)\.
- \[39\]H\. Lightman, V\. Kosaraju, Y\. Burda, H\. Edwards, B\. Baker, T\. Lee, J\. Leike, J\. Schulman, I\. Sutskever, and K\. Cobbe\(2023\)Let’s verify step by step\.arXiv preprint arXiv:2305\.20050\.Cited by:[4th item](https://arxiv.org/html/2609.38809#A7.I1.i4.p1.1),[§4\.1](https://arxiv.org/html/2609.38809#S4.SS1.p2.1.3)\.
- \[40\]J\. Zhou, T\. Lu, S\. Mishra, S\. Brahma, S\. Basu, Y\. Luan, D\. Zhou, and L\. Hou\(2023\)Instruction\-following evaluation for large language models\.arXiv preprint arXiv:2311\.07911\.Cited by:[5th item](https://arxiv.org/html/2609.38809#A7.I1.i5.p1.1),[§4\.1](https://arxiv.org/html/2609.38809#S4.SS1.p2.1.3)\.
- \[41\]A\. Hurst, A\. Lerer, A\. P\. Goucher, A\. Perelman, A\. Ramesh, A\. Clark, A\. Ostrow, A\. Welihinda, A\. Hayes, A\. Radford,et al\.\(2024\)Gpt\-4o system card\.arXiv preprint arXiv:2410\.21276\.Cited by:[§4\.1](https://arxiv.org/html/2609.38809#S4.SS1.p3.1.3)\.
- \[42\]H\. Yu, T\. Chen, J\. Feng, J\. Chen, W\. Dai, Q\. Yu, Y\. Zhang, W\. Ma, J\. Liu, M\. Wang, and H\. Zhou\(2026\)MemAgent: reshaping long\-context LLM with multi\-conv RL\-based memory agent\.InThe Fourteenth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=k5nIOvYGCL)Cited by:[2nd item](https://arxiv.org/html/2609.38809#A9.I1.i2.p1.1),[§4\.1](https://arxiv.org/html/2609.38809#S4.SS1.p3.1)\.
- \[43\]K\. Team, A\. Du, B\. Gao, B\. Xing, C\. Jiang, C\. Chen, C\. Li, C\. Xiao, C\. Du, C\. Liao,et al\.\(2025\)Kimi k1\. 5: scaling reinforcement learning with llms\.arXiv preprint arXiv:2501\.12599\.Cited by:[§F\.1](https://arxiv.org/html/2609.38809#A6.SS1.p1.3)\.

## Appendix ALimitations and Broader Impacts

### A\.1Limitations

Our work has several limitations\. First, all training data are derived from a single English dialogue dataset \(LoCoMo\), so the generalization of StateTree to other languages or dialogue domains remains to be validated\. Second, the Compositional StateTree relies on an LLM \(GPT\-4o\) to decompose questions and generate distractors; while we enforce structural validation, the quality of decomposition is bounded by the LLM’s capability and may introduce subtle semantic biases\. Finally, we use fixed binary\-tree depths \(D=2D\{=\}2andD=3D\{=\}3\) throughout training; adaptive depths or dynamic tree structures could further improve efficiency but are not explored here\.

### A\.2Broader Impacts

StateTree aims to improve the reliability of personalized assistants in long\-term interactions, which can enhance user experience in education, healthcare, and personal productivity\. However, more powerful reasoning capabilities could also be misused to extract sensitive information from conversation histories or enable unauthorized surveillance\. We encourage developers to deploy such systems with appropriate privacy safeguards, user consent mechanisms, and data retention policies\.

## Appendix BLicenses and Asset Usage

### B\.1Existing Assets

All existing datasets and models used in this paper are properly cited\. LoCoMo\[[15](https://arxiv.org/html/2609.38809#bib.bib12)\], LongMemEval\[[16](https://arxiv.org/html/2609.38809#bib.bib11)\], and PersonaMem are released for research purposes\. Qwen2\.5\-7B\-Instruct, Qwen2\.5\-14B\-Instruct, and Qwen3\-8B\[[35](https://arxiv.org/html/2609.38809#bib.bib35)\]are released under the Qwen License\. Qwen2\.5\-1\.5B\-Instruct, used as the LLM judge, is under the same license\. GPT\-4o is accessed via the OpenAI API\.

### B\.2LLM Usage Declaration

LLMs are used as non\-standard components in two parts of our methodology\. \(i\)Data construction:We use GPT\-4o \(temperature 0\.7\) to decompose target questions into semantic axes and generate distractor steps for the Compositional StateTree \(Section[3\.1](https://arxiv.org/html/2609.38809#S3.SS1)and Appendix[C\.4\.1](https://arxiv.org/html/2609.38809#A3.SS4.SSS1)\)\. \(ii\)Reward evaluation:We use Qwen2\.5\-1\.5B\-Instruct \(temperature 0\) as an LLM\-as\-a\-Judge evaluator within the combined reward function \(Section[3\.2](https://arxiv.org/html/2609.38809#S3.SS2)\)\.

## Appendix CDataset Construction Details

### C\.1Source Data

All training data are derived from the LoCoMo dataset\[[15](https://arxiv.org/html/2609.38809#bib.bib12)\], which contains multi\-session dialogues between two speakers\. Each conversation comprises approximately 13 sessions with interleavedDATE:markers indicating session timestamps\. We use the same 616 conversation–question pairs across all four curriculum stages; only the*task formulation*changes between stages\.

### C\.2Dataset Split

We filter out adversarial and empty\-answer questions, then split the remaining pairs 50/50\. The first half uses an 80/20 train/validation split \(616 and 154 samples\), and the second half forms the held\-out test set\.

The validation and test sets use the original direct QA format \(identical to the Warm\-up stage\) without any tree augmentation or record insertion\. This ensures that evaluation measures the model’s end\-task performance on clean conversation data\. The same training set of 616 samples is reused across all four curriculum stages; only the task formulation \(tree structure and prompt\) changes between stages\.

### C\.3Dataset Statistics and Construction Parameters

Table[9](https://arxiv.org/html/2609.38809#A3.T9)summarizes the dataset statistics and data construction parameters for each curriculum stage\.

Table 9:Dataset statistics and data construction parameters for each curriculum stage\. “UUID format” refers to the identifier format used for tree node keys\. “Insert mode” specifies where records are placed within the dialogue text\.ParameterWarm\-upStage 1Stage 2Stage 3Tree typeNone \(direct QA\)Basic StateTreeBasic StateTreeCompositional StateTreeTree depthDD–233Leaves–488Edge records061414Samples616616616616Avg\. length \(tokens\)∼\\sim10K∼\\sim10K∼\\sim10K∼\\sim10KUUID format–Standard UUID4Standard UUID4Standard UUID4Record format–\{UUID: VALUE\}\{UUID: VALUE\}\{UUID: \{step, next\}\}Insert mode–Inside speaker quotesInside speaker quotesInside speaker quotesTemporal discrimination–Yes \(session DATE\)Yes \(session DATE\)Yes \(session DATE\)Distractor pool size–64648 \(from decomposition\)

### C\.4Question Decomposition

For Stage 3 \(Compositional StateTree\), each target question is decomposed into a2×2×22\\times 2\\times 2hierarchy using an LLM\. Given a target question such as “When did Jon start expanding his studio’s social media presence?”, the decomposition produces three step fragments along semantic axes:

- •Step 1\(Person selection\):\[A\] Jon
- •Step 2\(Event category\):\[B\] expanding his studio’s social media presence
- •Step 3\(Question detail\):When did \[A\] start \[B\]?

The full decomposition tree for one conversation contains 8 such paths \(one per leaf\), each branching on person at level 1, event category at level 2, and question specificity at level 3\. Table[10](https://arxiv.org/html/2609.38809#A3.T10)shows the structure of a complete decomposition tree\.

Table 10:Semantic decomposition example for the target question “When did Jon start expanding his studio’s social media presence?” \(answer: “April, 2023”\)\.★\\bigstarmarks the target leaf\. The correct path aggregates: step\_1 = “\[A\] Jon”, step\_2 = “\[B\] expanding his studio’s social media presence”, step\_3 = “When did \[A\] start \[B\]?”, yielding the full question after substitution\.Level 1Level 2 \(Event\)Level 3 \(Question\)\[A\] Jon\[B\] expanding his studio’s social media presence★\\bigstarWhen did \[A\] start \[B\]?What did \[A\] do while \[B\]?\[B\] going to a fair for exposureWhen did \[A\] start \[B\]?What events did \[A\] participate in while \[B\]?\[A\] Gina\[B\] launching an ad campaignWhen did \[A\] start \[B\]?Why did \[A\] decide to start \[B\]?\[B\] teaming up with a local artistWhen did \[A\] start \[B\]?What did \[A\] do while \[B\]?#### C\.4\.1Decomposition LLM Prompt

To generate the2×2×22\\times 2\\times 2decomposition trees for Stage 3, we use GPT\-4o with temperature 0\.7\. Each target question is processed with the following system and user prompts\. The system prompt specifies the tree structure, output schema, and quality constraints; the user prompt provides the target question along with the full question pool for that conversation\.

Decomposition System Prompt \(Stage 3 Data Construction\)You are a dataset construction assistant\. Your task is to decompose a target question into a2×2×22\\times 2\\times 2binary discrimination tree for a reading comprehension benchmark\.The tree has 3 levels:•Level 1 \(root→\\to2 branches\): Person selection\. Each branch carries step\_1 = “\[A\] PersonName”•Level 2 \(each person→\\to2 branches\): Event category\. Each branch carries step\_2 = “\[B\] gerund\_phrase”\. The gerund phrase must be concrete and specific \(e\.g\., “attending the LGBTQ support group”\), NOT a vague category \(e\.g\., “community activities”\)\.•Level 3 \(each event→\\to2 branches\): Question specificity\. Each branch carries step\_3 = a question template that MUST contain BOTH \[A\] and \[B\] as placeholders\. The two questions under the same event MUST ask about different factual aspects\.CRITICAL: step\_3 must ask about CONCRETE FACTS that have definite answers — things like time, place, people involved, specific actions taken, specific results/outcomes, or specific objects\.GOOD examples \(factual\): “When did \[A\] \[B\]?”, “What did \[A\] make while \[B\]?”, “Where did \[A\] go for \[B\]?”BAD examples \(subjective/generic\): “How did \[A\] feel about \[B\]?”, “Why did \[A\] enjoy \[B\]?”Exactly ONE of the 8 leaves must be marked is\_target=true — the leaf whose step\_3, after substituting \[A\] and \[B\], yields \(or is semantically equivalent to\) the original target question\.Rules:1\.The target person MUST appear first in the tree\.2\.The target event MUST appear first under the target person\.3\.The target leaf MUST be the first leaf under the target event\.4\.Each event\_gerund should be a present participle phrase derived from an actual question in the pool\.5\.Every leaf’s “answer” field MUST be copied verbatim from a question in the pool\.6\.The two leaves under the same event MUST ask about genuinely DIFFERENT ASPECTS of the event\.7\.Events for the same person should be distinct and both grounded in the question pool\.8\.Events for the other person should also correspond to real pool questions but thematically contrast with the target person’s events\.9\.All answers must be short \(a few words or a short phrase\), copied from the pool\.10\.EVERY step\_3 MUST contain both \[A\] and \[B\] placeholders\.

Decomposition User Prompt Template \(Stage 3 Data Construction\)Target question \(row \{row\_index\}\):Q: \{target\_question\}sample\_id: \{sample\_id\}Speakers in this conversation:Speaker A: \{speaker\_a\}Speaker B: \{speaker\_b\}Below is the full question pool for this conversation \(\{num\_questions\} questions\)\. Use these to find suitable distractor questions and events\. Pick events and questions that are grounded in the actual conversation content\.— Question Pool —\{question\_pool\}— End of Question Pool —Please generate the2×2×22\\times 2\\times 2decomposition tree JSON for this target question\. Remember:•step\_2 must describe the EVENT/ACTIVITY itself, NOT reveal or hint at the answer•EVERY step\_3 MUST contain BOTH \[A\] and \[B\] placeholders•step\_3 must ask about CONCRETE FACTS•The target person and target event come first in the tree•Exactly 1 leaf is is\_target=true•Output raw JSON only, no markdown fencing

The question pool for each conversation is constructed by collecting all non\-adversarial QA pairs associated with that conversation in the LoCoMo dataset, including their answers and evidence session numbers\. Each generated decomposition is validated against a set of structural constraints \(correct number of persons, events, leaves; presence of \[A\]/\[B\] placeholders; exactly one target leaf; semantic diversity of sibling step\_3 values\) and regenerated if validation fails\.

### C\.5Distractor Question Pool

At each StateTree stage \(1–3\), non\-target leaves are populated with*distractor questions*from the same conversation and training split \(excluding the target\)\. Their semantic relevance to the dialogue makes them strong distractors\. For Stage 3, distractors are generated by the2×2×22\\times 2\\times 2decomposition \(Appendix[C\.4](https://arxiv.org/html/2609.38809#A3.SS4)\), with each non\-target leaf differing in at least one semantic axis\.

### C\.6Record Insertion Strategy

Tree edge records must be embedded naturally within the conversation text so that they blend into the dialogue flow\. We employ the following insertion strategy:

Insertion positions\.For all tree\-augmented stages \(Stages 1–3\), records are inserted*inside speaker quotations*: within lines of the formSpeaker said, "\.\.\.", records are placed at sentence boundaries \(after periods, exclamation marks, or question marks\) inside the quoted text\. This prevents artifacts such as a JSON record appearing immediately before aDATE:line or between speaker turns\.

Balanced session distribution\.Records are distributed across conversation sessions using a least\-loaded\-first allocation strategy\. For each record to be inserted, we:

1. 1\.Group available insertion slots by their enclosing session\.
2. 2\.Identify the session\(s\) with the fewest records already assigned\.
3. 3\.Randomly select a slot from the least\-loaded session\(s\)\.

Same\-key separation constraint\.When the same UUID key appears in two records \(as required by the temporal discrimination mechanism\), these two records are guaranteed to be inserted into*different*sessions\. This is enforced by tracking which sessions have already been used for each key and excluding them from the candidate set\.

Post\-insertion temporal ordering\.After all records are inserted, a verification pass checks each temporal discrimination fork: the correct\-path record must reside in a strictly more recent session \(by parsedDATE:timestamp\) than its distractor counterpart\. If any violation is detected, the two records’ positions in the context are swapped\. This swap procedure ensures the temporal ordering invariant holds regardless of the initial random placement\.

### C\.7Entity Key Pool for Ablation

In the*w/ Entity Keys*ablation \(Section[4\.4](https://arxiv.org/html/2609.38809#S4.SS4)\), each UUID is replaced with a high\-frequency concrete noun sampled without replacement from the 14\-word pool below\. This ensures that performance differences arise from semantic key content rather than topical relevance\.

Table 11:Entity key pool used in the*w/ Entity Keys*ablation\.gardenmirrortempleanchorlanternribboncandleshieldbridgecastlemeadowfeathersaddletrumpetFor example, underD=3D\{=\}3\(7 keys required\), a random draw might produce the edge records:

\{‘‘garden’’: ‘‘bridge’’\}, \{‘‘garden’’: ‘‘meadow’’\}, \{‘‘bridge’’: ‘‘castle’’\}, …

instead of the standard UUID format\{‘‘f391e945\-…’’: ‘‘8ada7089\-…’’\}\. The key pairing mechanism is preserved, but the model can now rely on the semantic familiarity of the word rather than performing pure string matching\.

## Appendix DFull Prompt Templates

### D\.1System Prompt

The following system prompt is used across all curriculum stages\. It instructs the model to produce a step\-by\-step reasoning trace enclosed in`<think\>\.\.\.</think\>`tags and place the final answer inside`\\boxed\{\.\.\.\}`\.

System PromptA conversation between User and Assistant\. The User asks a question, and the Assistant solves it\. The Assistant first thinks about the reasoning process in the mind and then provides the User with the answer\. The reasoning process is enclosed within <think\> </think\> and answer is enclosed within \\boxed\{\} tags, respectively, i\.e\., <think\> reasoning process here </think\> \\boxed\{answer here\}\.

### D\.2Warm\-up: Direct Dialogue QA

The Warm\-up prompt is identical to the official LoCoMo evaluation prompt\[[15](https://arxiv.org/html/2609.38809#bib.bib12)\]\.

Warm\-up PromptBased on the above conversations, write a short answer for the following question in a few words\. Do not write complete and lengthy sentences\. Answer with exact words from the conversations whenever possible\.Question:\{question\}

### D\.3Stage 1 & 2: Basic StateTree \(D=2D\{=\}2/D=3D\{=\}3\)

Stages 1 and 2 share the same prompt template; only the tree depth differs\.

Basic StateTree Prompt \(Stages 1 & 2\)In the conversation above, there are JSON records like\{‘‘KEY’’: ‘‘VALUE’’\}scattered throughout the dialogue text\. They form UUID chains: starting from a given key, each value either points to the next key \(a UUID\) or contains the final question to answer\.Your task: start from key‘‘\{root\_uuid\}’’and follow the chain to find the question, then answer it\.How to follow the chain:1\.Search the entire conversation for all records whose key matches the current UUID\.2\.Each record sits inside a specific session\. Look at the nearest preceding‘‘DATE: \.\.\.’’line to determine that record’s time\.3\.If the same key appears in multiple sessions, choose which record to use: among the remaining records, pick the one from the most recent session DATE\.4\.Read the chosen value:•If it is a UUID, treat it as the next key and go back to step 1\.•If it is a natural\-language question, that is the question you must answer\.5\.Once you find the question, answer it based on the conversation content\.

### D\.4Stage 3: Compositional StateTree \(D=3D\{=\}3\)

Compositional StateTree Prompt \(Stage 3\)In the conversation above, there are JSON records like\{‘‘UUID’’: \{‘‘step’’: ‘‘\.\.\.’’, ‘‘next’’: ‘‘UUID’’\}\}scattered throughout the dialogue text\. They form a decision tree\.Each record maps a UUID key to a JSON object with:•‘‘step’’: a piece of information to accumulate along the path•‘‘next’’: the UUID of the next node to follow \(absent at leaf nodes\)Your task: start from key‘‘\{root\_uuid\}’’and follow the tree to a leaf, accumulating the step information at each edge\. Then answer the question\.How to follow the tree:1\.Search the entire conversation for all records whose key matches the current UUID\.2\.Each record sits inside a specific session\. Look at the nearest preceding‘‘DATE: \.\.\.’’line to determine that record’s session time\.3\.If the same key appears in multiple sessions, pick the record from the most recent session DATE\.4\.Read the‘‘step’’field and remember it\.5\.If a‘‘next’’field exists, use it as the new key and go back to step 1\.6\.If no‘‘next’’field exists, you have reached a leaf\.Once you reach a leaf, aggregate all the step information you collected along the path to form the final question\. Then answer that question step by step based on the conversation content\.

### D\.5CoT Prompt Baseline

For the*w/ CoT prompt*ablation variant \(Section[4\.4](https://arxiv.org/html/2609.38809#S4.SS4)\), we modify the System Prompt to explicitly encourage step\-by\-step reasoning, without any StateTree structure or RL training\. This baseline tests whether generic reasoning prompts can replicate the gains from explicit structural navigation\.

CoT System PromptA conversation between User and Assistant\. The User asks a question, and the Assistant solves it\. The Assistant first thinks about the reasoning processstep by stepin the mind, carefully analyzing the question and searching through the conversation for relevant information\. Then the Assistant provides the User with the answer\. The reasoning process is enclosed within <think\> </think\> and answer is enclosed within \\boxed\{\} tags, respectively, i\.e\., <think\> reasoning process here </think\> \\boxed\{answer here\}\.

### D\.6LLM Evaluation Prompts

#### D\.6\.1LoCoMo Evaluation Prompt

LoCoMo LLM Judge PromptYour task is to label an answer to a question as "CORRECT" or "WRONG"\.You will be given the following data: \(1\) a question \(posed by one user to another user\), \(2\) a ’gold’ \(ground truth\) answer, \(3\) a generated answer which you will score as CORRECT/WRONG\.The point of the question is to ask about something one user should know about the other user based on their prior conversations\. The gold answer will usually be a concise and short answer that includes the referenced topic, for example:Question: Do you remember what I got the last time I went to Hawaii?Gold answer: A shell necklaceThe generated answer might be much longer, but you should be generous with your grading — as long as it touches on the same topic as the gold answer, it should be counted as CORRECT\.For time related questions, the gold answer will be a specific date, month, year, etc\. The generated answer might be much longer or use relative time references \(like ’last Tuesday’ or ’next month’\), but you should be generous with your grading — as long as it refers to the same date or time period as the gold answer, it should be counted as CORRECT\. Even if the format differs \(e\.g\., ’May 7th’ vs ’7 May’\), consider it CORRECT if it’s the same date\.Now it’s time for the real question:Question:\{question\}Gold answer:\{gold\_answer\}Generated answer:\{generated\_answer\}Return the label CORRECT or WRONG in a json format with the key as "label"\. Do NOT include both CORRECT and WRONG in your response, or it will break the evaluation script\.

#### D\.6\.2LongMemEval Evaluation Prompts

LongMemEval contains multiple task categories, each with a dedicated judge prompt\.

LongMemEval Standard Tasks PromptI will give you a question, a correct answer, and a response from a model\. Please answer yes if the response contains the correct answer\. Otherwise, answer no\. If the response is equivalent to the correct answer or contains all the intermediate steps to get the correct answer, you should also answer yes\. If the response only contains a subset of the information required by the answer, answer no\.Question:\{question\}Correct Answer:\{answer\}Model Response:\{response\}Is the model response correct? Answer yes or no only\.

LongMemEval Temporal Reasoning PromptI will give you a question, a correct answer, and a response from a model\. Please answer yes if the response contains the correct answer\. Otherwise, answer no\. If the response is equivalent to the correct answer or contains all the intermediate steps to get the correct answer, you should also answer yes\. If the response only contains a subset of the information required by the answer, answer no\. In addition, do not penalize off\-by\-one errors for the number of days\. If the question asks for the number of days/weeks/months, etc\., and the model makes off\-by\-one errors \(e\.g\., predicting 19 days when the answer is 18\), the model’s response is still correct\.Question:\{question\}Correct Answer:\{answer\}Model Response:\{response\}Is the model response correct? Answer yes or no only\.

LongMemEval Knowledge Update PromptI will give you a question, a correct answer, and a response from a model\. Please answer yes if the response contains the correct answer\. Otherwise, answer no\. If the response contains some previous information along with an updated answer, the response should be considered as correct as long as the updated answer is the required answer\.Question:\{question\}Correct Answer:\{answer\}Model Response:\{response\}Is the model response correct? Answer yes or no only\.

LongMemEval Single\-session Preference PromptI will give you a question, a rubric for desired personalized response, and a response from a model\. Please answer yes if the response satisfies the desired response\. Otherwise, answer no\. The model does not need to reflect all the points in the rubric\. The response is correct as long as it recalls and utilizes the user’s personal information correctly\.Question:\{question\}Rubric:\{answer\}Model Response:\{response\}Is the model response correct? Answer yes or no only\.

## Appendix EExamples of Inserted Records in Context

This section illustrates how tree records are embedded within conversation text at each stage\.

### E\.1Basic StateTree Record \(Stages 1 & 2\)

#### E\.1\.1Case Study

In the Basic StateTree, each record is a flat key\-value pair\{UUID: VALUE\}inserted at a natural dialogue boundary\. The value is either another UUID \(internal node\) or a natural\-language question \(leaf node\)\.

Basic StateTree: Record Inserted in DialogueCaroline said, “Thanks, Melanie\!\{‘‘95c49518\-3f28\-45f4\-85be\-de9a66ea5fd9’’: ‘‘What are Caroline’s plans for the summer?’’\}\.I really appreciate it\. Excited for the future\! Bye\!”

In this example, the UUID key95c49518\.\.\.maps directly to a question string, indicating a leaf node\. If this were an internal node, the value would be another UUID pointing to the next hop\.

The example below illustrates a concrete instance withD=2D\{=\}2\.

Greenmarks the correct path to leaf \(target question\);redmarks distractor path to distractor leaves\.

Example of StateTree\-augmented dialogue input \(BasicD=2D\{=\}2\)Session 1 —2:24 pm, 14 Aug, 2023 Caroline:That pic is cool\! Representing inclusivity and diversity in my art is important to me\.\{"113464e2\-8d54\-493c\-874a\-ebb3c07b9d48": "5ab90ad1\-5990\-4820\-9aec\-6525e8e2867e"\}I also use it to speak up for the community and push for acceptance\. Here’s a recent painting\! … Session 2 —1:56 pm, 8 May, 2023 Melanie:So cool you found such a helpful group\. What’s it done for you?\{"113464e2\-8d54\-493c\-874a\-ebb3c07b9d48": "9320b92a\-cb63\-4ed7\-b22e\-d3521da21950"\}… Session 3 —8:18 pm, 6 July, 2023 Caroline:Glad you have support, Caroline\!\{"5ab90ad1\-5990\-4820\-9aec\-6525e8e2867e": "When did Melanie paint a sunrise?"\}How’s it going? … Session 4 —7:55 pm, 9 June, 2023 Melanie:Glad you have support, Caroline\!\{"5ab90ad1\-5990\-4820\-9aec\-6525e8e2867e": "What pets does Melanie have?"\}Unconditional love … Session 5 —1:50 pm, 17 Aug, 2023 Caroline:Sounds great, Mel\!\{"9320b92a\-cb63\-4ed7\-b22e\-d3521da21950": "What kind of pot did Mel and her kids make with clay?"\}We’ll … Session 6 —1:36 pm, 3 July, 2023 Melanie:Wow, Caroline\! That’s great\! I just signed up for a pottery class yesterday\. It’s like therapy for me, letting me express myself and get creative\.\{"9320b92a\-cb63\-4ed7\-b22e\-d3521da21950": "Would Melanie go on another roadtrip soon?"\}Have you … Instruction:In the dialogue above, a correct question is hidden within key:value records encoded with UUID strings\. Starting from key113464e2\-8d54\-493c\-874a\-ebb3c07b9d48, locate each record, resolve forks by selecting the edge record in the most recent session, follow the path to a leaf, then answer the recovered question\.Walkthrough\.Starting from root key113464e2\-8d54\-493c\-874a\-ebb3c07b9d48, the model finds two records in Session 1 \(Aug 14\) and Session 2 \(May 8\)\. Session 1 is more recent, so it follows5ab90ad1\-5990\-4820\-9aec\-6525e8e2867e\. Next, it finds records for5ab90ad1\-5990\-4820\-9aec\-6525e8e2867ein Session 3 \(July 6\) and Session 4 \(June 9\)\. Session 3 is more recent, leading to the leaf “When did Melanie paint a sunrise?”\. The model answers this question from the dialogue content\.

### E\.2Compositional StateTree Record \(Stage 3\)

In the Compositional StateTree, each record is a nested JSON object carrying astepfield \(the semantic fragment\) and optionally anextfield \(the UUID of the child node\)\.

Compositional StateTree: Records Inserted in Dialogue\(Root node \- Level 1, person selection\)…cherishing those happy moments and clinging to them is key\.”\{‘‘84858d3a\-1f30\-41cd\-9882\-afe161ca4970’’: \{‘‘step’’: ‘‘\[A\] Caroline’’, ‘‘next’’: ‘‘8ada7089\-43a6\-404c\-b249\-3d778e012633’’\}\}\.Melanie said, “Yeah, same here Caroline\.”\(Internal node \- Level 2, event selection\)…“I’ve been thinking about volunteering more at the community center\.”\{‘‘8ada7089\-43a6\-404c\-b249\-3d778e012633’’: \{‘‘step’’: ‘‘\[B\] expanding his studio’s social media presence’’, ‘‘next’’: ‘‘6916ce1a\-c2d0\-4146\-9e8d\-185110a68332’’\}\}\.Caroline said, “That sounds like a great idea\!”\(Leaf node \- Level 3, no “next” field\)…“Reminds me it’s important to cultivate a loving and accepting environment\.”\{‘‘6916ce1a\-c2d0\-4146\-9e8d\-185110a68332’’: \{‘‘step’’: ‘‘When did \[A\] start \[B\]?’’\}\}\.and shared a photo of a group of people…

The root record providesstep: "\[A\] Caroline"\(person selection\), the intermediate record providesstep: "\[B\] expanding his studio’s social media presence"\(event selection\), and the leaf record providesstep: "When did \[A\] start \[B\]?"\(question detail\) with nonextfield\. By following the correct path and aggregating all steps, the model reconstructs the full question\.

## Appendix FHyperparameters and Training Configuration

### F\.1Group Relative Policy Optimization \(GRPO\)

We adopt GRPO to train our model\. For each questionqq, its long contextℒ\\mathcal\{L\}\(the StateTree\-augmented dialogue𝒮′\\mathcal\{S\}^\{\\prime\}defined in Section[3\.1](https://arxiv.org/html/2609.38809#S3.SS1)\), and its ground\-truth answeraafrom a dataset𝒟\\mathcal\{D\}, GRPO samples a group of rollout trajectories\{o1,o2,⋯,oG\}\\\{o\_\{1\},o\_\{2\},\\cdots,o\_\{G\}\\\}from the old policyπθo​l​d\\pi\_\{\\theta\_\{old\}\}\. The policyπθ\\pi\_\{\\theta\}is then optimized by maximizing:

JGRPO​\(θ\)\\displaystyle\\\!\\\!\\\!J\_\{\\text\{GRPO\}\}\(\\theta\)=𝔼\(ℒ,q,a\)∼𝒟,\{oi\}i=1G∼πθold\(⋅\|ℒ,q\)\\displaystyle=\\mathbb\{E\}\_\{\(\\mathcal\{L\},q,a\)\\sim\\mathcal\{D\},\\,\\\{o\_\{i\}\\\}\_\{i=1\}^\{G\}\\sim\\pi\_\{\\theta\_\{\\text\{old\}\}\}\(\\cdot\|\\mathcal\{L\},q\)\}\[1G∑i=1G1\|oi\|∑t=1\|oi\|\\displaystyle\\Bigg\[\\frac\{1\}\{G\}\\\!\\sum\_\{i=1\}^\{G\}\\\!\\frac\{1\}\{\|o\_\{i\}\|\}\\\!\\sum\_\{t=1\}^\{\|o\_\{i\}\|\}\\\!\(min\[ρi,t\(θ\)Ai,clip\(ρi,t\(θ\),−ε,\+ε\)Ai\]−βDKL\(πθ\(⋅\|q,oi,<t\)∥πref\(⋅\|q,oi,<t\)\)\)\]\\displaystyle\\Big\(\\\!\\min\\big\[\\rho\_\{i,t\}\(\\theta\)A\_\{i\},\\mathrm\{clip\}\(\\rho\_\{i,t\}\(\\theta\),1\\\!\-\\\!\\varepsilon,1\\\!\+\\\!\\varepsilon\)A\_\{i\}\\big\]\\\!\-\\\!\\beta D\_\{\\text\{KL\}\}\\big\(\\pi\_\{\\theta\}\(\\cdot\|q,o\_\{i,<t\}\)\\\|\\pi\_\{\\text\{ref\}\}\(\\cdot\|q,o\_\{i,<t\}\)\\big\)\\Big\)\\Bigg\]\\\!\\\!\(2\)whereρi,t​\(θ\)=πθ​\(oi,t\|q,oi,<t\)πθold​\(oi,t\|q,oi,<t\)\\rho\_\{i,t\}\(\\theta\)=\\frac\{\\pi\_\{\\theta\}\(o\_\{i,t\}\|q,o\_\{i,<t\}\)\}\{\\pi\_\{\\theta\_\{\\text\{old\}\}\}\(o\_\{i,t\}\|q,o\_\{i,<t\}\)\}\. Hyperparametersε\\varepsilonandβ\\betacontrol the clipping range of the importance sampling ratio and the weight of the KL penalty term, respectively\. The advantageAiA\_\{i\}is computed by normalizing the trajectory rewards\{r1,r2,…,rG\}\\\{r\_\{1\},r\_\{2\},\\dots,r\_\{G\}\\\}for each rollout trajectory:

Ai=ri−mean​\(\{r1,r2,⋯,rG\}\)std​\(\{r1,r2,⋯,rG\}\)\\displaystyle A\_\{i\}=\\frac\{r\_\{i\}\-\\text\{mean\}\(\\\{r\_\{1\},r\_\{2\},\\cdots,r\_\{G\}\\\}\)\}\{\\text\{std\}\(\\\{r\_\{1\},r\_\{2\},\\cdots,r\_\{G\}\\\}\)\}\(3\)Here,rir\_\{i\}is the reward for trajectoryoio\_\{i\}\. Following\[[24](https://arxiv.org/html/2609.38809#bib.bib34),[43](https://arxiv.org/html/2609.38809#bib.bib26)\], we use a combined reward function to assignrir\_\{i\}and mitigate reward hacking\.

Training hyperparameters are provided in Section[3\.2](https://arxiv.org/html/2609.38809#S3.SS2)of the main text\. Each experiment is run three times with different random seeds, and we report the average results across runs\.

### F\.2Compute Resources

All training runs are performed on an internal cluster with 32×\\timesNVIDIA H20 GPUs \(96 GB\)\. The training times are approximately 90 hours for Qwen2\.5\-7B\-Instruct, 100 hours for Qwen3\-8B, and 160 hours for Qwen2\.5\-14B\-Instruct\.

## Appendix GEvaluation Details

### G\.1Benchmark Descriptions

- •LoCoMo\[[15](https://arxiv.org/html/2609.38809#bib.bib12)\]: A multi\-session dialogue benchmark with four reasoning categories: Multi Hop, Temporal, Open Domain, and Single Hop\. Input lengths are approximately 10K tokens\. We report Accuracy, token\-level F1, and BLEU\-1\.
- •LongMemEval\[[16](https://arxiv.org/html/2609.38809#bib.bib11)\]: An out\-of\-domain benchmark evaluating six dimensions of long\-term memory: Temporal reasoning, Multi\-Session reasoning, Knowledge Update, and three Single\-Session categories \(User, Assistant, Preference\)\. Input lengths range from 16K to 100K tokens\. For readability, Table[3](https://arxiv.org/html/2609.38809#S4.T3)abbreviates these categories as Temp\., Multi\-Ses\., Know\. Upd\., SS\-User, SS\-Asst\., and SS\-Pref\., respectively\.
- •MMLU\[[38](https://arxiv.org/html/2609.38809#bib.bib24)\]: A multiple\-choice benchmark covering 57 academic subjects, testing general knowledge and reasoning\.
- •MATH\-500\[[39](https://arxiv.org/html/2609.38809#bib.bib25)\]: A curated subset of 500 competition\-level mathematics problems\.
- •IFEval\[[40](https://arxiv.org/html/2609.38809#bib.bib5)\]: An instruction\-following evaluation measuring the model’s ability to comply with specific formatting and content constraints\.
- •PersonaMem\[[27](https://arxiv.org/html/2609.38809#bib.bib23)\]: A benchmark for evaluating dynamic user profiling and personalized responses at scale, measuring the model’s ability to track preference evolution, recall shared facts, and provide preference\-aligned recommendations across multi\-turn conversations\. Input lengths range from 32K to 128K tokens\. We report exact\-match accuracy\. Table[3](https://arxiv.org/html/2609.38809#S4.T3)abbreviates the seven task dimensions as Latest Pref\. \(Acknowledge Latest User Preferences\), New Scen\. \(Generalize to New Scenarios\), Align\. Rec\. \(Provide Preference\-Aligned Recommendations\), Shared Fact \(Recall User Shared Facts\), Revisit Reas\. \(Revisit Reasons Behind Preference Updates\), New Idea \(Suggest New Ideas\), and Track Evol\. \(Track Full Preference Evolution\)\.

### G\.2Inference Configuration

For all evaluations, we use temperature 0\.6, maximum input length of 128K tokens, and maximum output length of 4096 tokens\.

### G\.3Additional OOD Results

On PersonaMem 32k \(Table[12](https://arxiv.org/html/2609.38809#A7.T12)\), StateTree\-14B achieves 64\.52% average accuracy \(\+5\.61% over base\), with particularly strong performance on recalling update reasons \(86\.87%\), aligning with the StateTree’s explicit tracking of state transitions\.

Table 12:Performance comparison across different models on OOD PersonaMem\-32k\.ModelGeneralizingto NewScenariosProvide PreferenceAlignedRecommendationsRecall UserSharedFactsRecalling FactsMentioned bythe UserRecalling the ReasonsBehind PreviousUpdatesSuggestNewIdeasTrack FullPreferenceEvolutionAverageQwenLong\-L1\-32B71\.9365\.4567\.4452\.9478\.7922\.5874\.8263\.84R1\-Distill\-Qwen\-32B56\.1461\.8261\.2464\.7183\.8422\.5879\.1462\.82Qwen2\.5\-7B\-Instruct52\.6360\.0041\.8652\.9479\.8017\.2066\.1953\.14SEALONG\-7B56\.1454\.5541\.0947\.0682\.8317\.2064\.7552\.80LoongRL\-7B59\.6569\.0948\.8464\.7178\.7920\.4372\.6658\.40RL\-MemAgent\-7B52\.6349\.0947\.2976\.4779\.8034\.4157\.5554\.67StateTree\-7B68\.4263\.6449\.6176\.4782\.8327\.9673\.3861\.29Qwen2\.5\-14B\-Instruct75\.4456\.3656\.5964\.7178\.7916\.1369\.0658\.91SEALONG\-14B64\.9156\.3655\.0470\.5977\.7813\.9869\.7857\.39LoongRL\-14B64\.9165\.4565\.8970\.5980\.8115\.0570\.5061\.46RL\-MemAgent\-14B68\.4265\.4551\.1670\.5983\.8418\.2868\.3559\.08StateTree\-14B75\.4461\.8265\.8976\.4786\.8720\.4371\.9464\.52Qwen3\-8B66\.6754\.5555\.8152\.9485\.8618\.2866\.1958\.23StateTree\-8B71\.9363\.6460\.4758\.8288\.8920\.4371\.2262\.82

## Appendix HCategory\-Level Curriculum Ablation

Tables[13](https://arxiv.org/html/2609.38809#A8.T13)and[14](https://arxiv.org/html/2609.38809#A8.T14)report the per\-category breakdown of the curriculum stage ablation on LoCoMo and LongMemEval, respectively\.

Table 13:Category\-level curriculum ablation on LoCoMo \(7B\)\.VariantMulti HopTemporalOpen DomainSingle HopAverageQwen2\.5\-7B\-Instruct63\.7723\.9050\.0044\.9244\.29StateTree\-7B \(full\)64\.4932\.7056\.0050\.3549\.61w/o warm\-up62\.3227\.6750\.0045\.6345\.19w/o Stage 1 \(D=2D\{=\}2\)63\.0424\.5350\.0045\.6344\.68w/o Stage 2 \(D=3D\{=\}3\)60\.1428\.9352\.0047\.5246\.23w/o Stage 3 \(Comp\.\)60\.8729\.5652\.0047\.9946\.75

Table 14:Category\-level curriculum ablation on LongMemEval \(7B\)\.VariantTemporalMulti\-SessionKnowledge UpdateSingle\-Session UserSingle\-Session AssistantSingle\-Session PreferenceAverageQwen2\.5\-7B\-Instruct20\.308\.2752\.5625\.7137\.503\.3323\.80StateTree\-7B \(full\)29\.3231\.5867\.9575\.7176\.7923\.3347\.40w/o warm\-up27\.8228\.5764\.1068\.5767\.8613\.3343\.00w/o Stage 1 \(D=2D\{=\}2\)24\.8125\.5662\.8271\.4373\.2120\.0042\.60w/o Stage 2 \(D=3D\{=\}3\)26\.3228\.5764\.1072\.8673\.2120\.0044\.20w/o Stage 3 \(Comp\.\)27\.0728\.5765\.3872\.8675\.0020\.0044\.80

Stage\-wise contributions\.Warm\-up delivers the largest gains on Open Domain, Single\-Session User/Assistant/Preference, and foundational QA\. Stage 1 \(D=2D\{=\}2\) dominates Temporal and Multi\-Session reasoning, indicating that shallow cross\-session discrimination is the minimal effective structure for these capabilities\. Stage 2 \(D=3D\{=\}3\) provides the largest Multi\-Hop gains on LoCoMo, while Stage 3 \(Compositional\) contributes more uniformly across categories, consolidating prior skills through semantic decomposition\. In aggregate, the contribution rank order is Stage 1\>\>Warm\-up\>\>Stage 2\>\>Stage 3 on both benchmarks \(LoCoMo: \+4\.93 / \+4\.42 / \+3\.38 / \+2\.86; LongMemEval: \+4\.80 / \+4\.40 / \+3\.20 / \+2\.60\), confirming that shallow temporal discrimination and QA grounding are the most critical components, with deeper compositional stages yielding diminishing but appreciable marginal returns\.

## Appendix IBaseline Implementation Details

To ensure a fair comparison, we clarify the evaluation setup for each baseline:

- •SEALONG\[[29](https://arxiv.org/html/2609.38809#bib.bib21)\]: We evaluate using the officially released checkpoints provided by the authors\.
- •RL\-MemAgent\[[42](https://arxiv.org/html/2609.38809#bib.bib31)\]: We evaluate using the officially released checkpoints provided by the authors\.
- •LoongRL\[[33](https://arxiv.org/html/2609.38809#bib.bib13)\]: Since their model checkpoints are not publicly available, we re\-train their method using their publicly released dataset on the Qwen2\.5 base models, following their published training configuration\.

## Appendix JComplete Training Examples

This section shows training inputs for LoCoMo sampleconv\-26\(“What is Caroline’s identity?”\)\. Only turns containing tree records are shown\.

### J\.1Basic StateTree Training

The following Stage 2 sample uses flat\{UUID: VALUE\}records embedded in speaker quotations, where values are either UUIDs \(internal nodes\) or questions \(leaves\)\.

Basic StateTree Training InputDATE: 2:24 pm on 14 August, 2023Caroline said, “It was so inspiring, Mel\! Check out the crowd\.\{"387c1508\-38e1\-43f0\-a36d\-ce8cba77a4c9": "37cbcf3a\-944f\-45cd\-b647\-e5e12f51d593"\}\. People of all kinds celebrating love and acceptance \- it really pushed me to keep fighting for LGBTQ rights\.”DATE: 4:33 pm on 12 July, 2023Melanie said, “Caroline, so glad you got the support\! Your experience really brought you to where you need to be\. You’re gonna make a huge difference\!\{"77376180\-3363\-4fa3\-95d7\-f21859335c9e": "What does Melanie do to destress?"\}\. This book I read last year reminds me to always pursue my dreams, just like you are doing\!”DATE: 8:18 pm on 6 July, 2023Melanie said, “Glad you have support, Caroline\! Unconditional love is so important\. Here’s a pic of my family camping at the beach\.\{"37cbcf3a\-944f\-45cd\-b647\-e5e12f51d593": "What is Caroline’s identity?"\}\. We love it, it brings us closer\!”DATE: 1:36 pm on 3 July, 2023Melanie said, “Wow, Caroline, sounds like the parade was an awesome experience\!\{"37cbcf3a\-944f\-45cd\-b647\-e5e12f51d593": "What was the poetry reading that Caroline attended about?"\}\. It’s great to see the love and support for the LGBTQ\+ community\. Congrats\! Has this experience influenced your goals at all?”DATE: 1:14 pm on 25 May, 2023Caroline said, “I chose them ’cause they help LGBTQ\+ folks with adoption\. Their inclusivity and support really spoke to me\.\{"387c1508\-38e1\-43f0\-a36d\-ce8cba77a4c9": "77376180\-3363\-4fa3\-95d7\-f21859335c9e"\}\.”DATE: 1:56 pm on 8 May, 2023Melanie said, “That’s really cool\.\{"77376180\-3363\-4fa3\-95d7\-f21859335c9e": "When did Melanie’s friend adopt a child?"\}\. You’ve got guts\. What now?”In the conversation above, there are JSON records like "KEY": "VALUE" scattered throughout the dialogue text\. They form UUID chains: starting from a given key, each value either points to the next key \(a UUID\) or contains the final question to answer\.Your task: start from key "387c1508\-38e1\-43f0\-a36d\-ce8cba77a4c9" and follow the chain to find the question, then answer it\.How to follow the chain:1\. Search the entire conversation for all records whose key matches the current UUID\.2\. Each record sits inside a specific session\. Look at the nearest preceding "DATE: …" line to determine that record’s time\.3\. If the same key appears in multiple sessions, choose which record to use:\- Among the remaining records, pick the one from the most recent session DATE\.4\. Read the chosen value:\- If it is a UUID, treat it as the next key and go back to step 1\.\- If it is a natural\-language question, that is the question you must answer\.5\. Once you find the question, answer it based on the conversation content\.

Chain head UUID:387c1508\-38e1\-43f0\-a36d\-ce8cba77a4c9 Question:What is Caroline’s identity? Answer:Transgender woman

Correct path\(2 edges\):

1. 1\.\{‘‘387c1508\-38e1\-43f0\-a36d\-ce8cba77a4c9’’: ‘‘37cbcf3a\-944f\-45cd\-b647\-e5e12f51d593’’\}\[SESSION: 2:24 pm on 14 August, 2023\]
2. 2\.\{‘‘37cbcf3a\-944f\-45cd\-b647\-e5e12f51d593’’: ‘‘What is Caroline’s identity?’’\}\[SESSION: 8:18 pm on 6 July, 2023\]

Temporal discrimination forks\(correct\-path edges are the most recent among records sharing the same key\):

- •Depth 0\(UUID387c1508\-38e1\-43f0\-a36d\-ce8cba77a4c9\): - –Correct edge:37cbcf3a\-944f\-45cd\-b647\-e5e12f51d593\[2:24 pm on 14 August, 2023\] - –Distractor edge:77376180\-3363\-4fa3\-95d7\-f21859335c9e\[1:14 pm on 25 May, 2023\]
- •Depth 1\(UUID37cbcf3a\-944f\-45cd\-b647\-e5e12f51d593\): - –Correct edge: “What is Caroline’s identity?” \[8:18 pm on 6 July, 2023\] - –Distractor edge: “What was the poetry reading that Caroline attended about?” \[1:36 pm on 3 July, 2023\]

Table 15:StateTree structure for theD=2D\{=\}2Basic StateTree sample \(conv\-26\)\.★\\bigstarmarks the target leaf\.Level 1 \(Root\)Level 2 \(Next\)Level 3 \(Question\)387c1508\-38e1\-43f0\-a36d\-ce8cba77a4c937cbcf3a\-944f\-45cd\-b647\-e5e12f51d593★\\bigstarWhat is Caroline’s identity?What was the poetry reading that Caroline attended about?77376180\-3363\-4fa3\-95d7\-f21859335c9eWhat does Melanie do to destress?When did Melanie’s friend adopt a child?The 6 edge records are distributed across 6 distinct sessions \(one per session\)\.

### J\.2Compositional StateTree Training \(Stage 3\)

The following Stage 3 sample uses nested\{UUID: \{‘‘step’’, ‘‘next’’\}\}records in speaker quotations, wherestepcarries a semantic fragment andnextpoints to the child UUID \(absent at leaves\)\.

Compositional StateTree Training InputDATE: 3:31 pm on 23 August, 2023Caroline said, “Thanks, Melanie\! I really appreciate it\. Excited for the future\!\{"4c6f1497\-b881\-46a7\-8cc4\-aba5fbac5429": \{"step": "\[A\] Caroline", "next": "1616ef6c\-b7ed\-4908\-bbf4\-cfa532591f0c"\}\}\. Bye\!”DATE: 1:50 pm on 17 August, 2023Caroline said, “Sure thing, Melanie\!\{"97ae53c4\-dd29\-4d61\-bf87\-140b35e082ac": \{"step": "\[B\] running a charity race", "next": "59b5b99c\-03f2\-4abc\-8331\-cfb5119c720b"\}\}\. Can’t wait to see your pottery project\. I’m happy you found something that makes you happy\. Show me when you can\!”DATE: 2:24 pm on 14 August, 2023Melanie said, “Wow, Caroline, that’s so cool\!\{"4c6f1497\-b881\-46a7\-8cc4\-aba5fbac5429": \{"step": "\[A\] Melanie", "next": "97ae53c4\-dd29\-4d61\-bf87\-140b35e082ac"\}\}\. Art can be so healing and a way to really connect with who you are\. It’s awesome that beauty can be found in the imperfections\. We’re all individual and wonderfully imperfect\. Thanks for sharing it with me\!”DATE: 8:56 pm on 20 July, 2023Caroline said, “Sounds fun\! What was the best part? Do you do it often with the kids?\{"59b5b99c\-03f2\-4abc\-8331\-cfb5119c720b": \{"step": "What did \[B\] that \[A\] was part of raise awareness for?"\}\}\.”DATE: 2:31 pm on 17 July, 2023Melanie said, “Wow, Caroline, that painting is awesome\! Those colors are so vivid and the whole thing looks really unified\. What inspired you?\{"1616ef6c\-b7ed\-4908\-bbf4\-cfa532591f0c": \{"step": "\[B\] discussing her identity", "next": "da0f6e17\-39f3\-460f\-848a\-eb3375327559"\}\}\.”DATE: 1:51 pm on 15 July, 2023Caroline said, “Wow, nice pic\!\{"87801b39\-e9da\-4bac\-a1a8\-e272d4931144": \{"step": "What did \[A\] learn while \[B\]?"\}\}\. You both looked amazing\. One special memory for me was this pride parade I went to a few weeks ago\.”DATE: 4:33 pm on 12 July, 2023Melanie said, “Thanks, Caroline\!\{"5fa0b1cb\-87a6\-4a2f\-8a75\-5db870313798": \{"step": "What types of paintings has \[A\] done related to \[B\]?"\}\}\. This has been great for my mental health\. I’m gonna keep it up\.”DATE: 8:18 pm on 6 July, 2023Melanie said, “Glad you have support, Caroline\! Unconditional love is so important\. Here’s a pic of my family camping at the beach\.\{"87801b39\-e9da\-4bac\-a1a8\-e272d4931144": \{"step": "When did \[A\] start \[B\]?"\}\}\. We love it, it brings us closer\!”DATE: 1:36 pm on 3 July, 2023Caroline said, “Cool, thanks Mel\! Can’t wait\. I’ll keep ya posted\. Bye\!\{"da0f6e17\-39f3\-460f\-848a\-eb3375327559": \{"step": "What is \[A\]’s identity while \[B\]?"\}\}\.”DATE: 10:37 am on 27 June, 2023Melanie said, “Congrats Caroline\! Good on you for going after what you really care about\.\{"1616ef6c\-b7ed\-4908\-bbf4\-cfa532591f0c": \{"step": "\[B\] researching adoption agencies", "next": "87801b39\-e9da\-4bac\-a1a8\-e272d4931144"\}\}\.”DATE: 7:55 pm on 9 June, 2023Melanie said, “Yeah, Caroline\!\{"97ae53c4\-dd29\-4d61\-bf87\-140b35e082ac": \{"step": "\[B\] painting a sunset", "next": "5fa0b1cb\-87a6\-4a2f\-8a75\-5db870313798"\}\}\. It takes courage to talk about our own stories\. But it’s in these vulnerable moments that we bond and understand each other\. We all have our different paths, but if we share them, we show people that they’re not alone\. Our stories can be so inspiring and encouraging to others who are facing the same challenges\. Thank you for using your voice to create love, acceptance, and hope\. You’re doing amazing\!”Melanie said, “Absolutely, Caroline\!\{"5fa0b1cb\-87a6\-4a2f\-8a75\-5db870313798": \{"step": "What did \[A\] paint while \[B\]?"\}\}\. I cherish time with family\. It’s when I really feel alive and happy\.”DATE: 1:14 pm on 25 May, 2023Melanie said, “That’s great, Caroline\! Loving the inclusivity and support\.\{"da0f6e17\-39f3\-460f\-848a\-eb3375327559": \{"step": "What career paths is \[A\] considering while \[B\]?"\}\}\. Anything you’re excited for in the adoption process?”DATE: 1:56 pm on 8 May, 2023Caroline said, “I went to a LGBTQ support group yesterday and it was so powerful\.\{"59b5b99c\-03f2\-4abc\-8331\-cfb5119c720b": \{"step": "When did \[A\] participate in \[B\]?"\}\}\.”

Root UUID:4c6f1497\-b881\-46a7\-8cc4\-aba5fbac5429 Original question:What is Caroline’s identity? Answer:Transgender woman

Correct path\(3 edges\):

1. 1\.Level 1:\{‘‘4c6f1497\-b881\-46a7\-8cc4\-aba5fbac5429’’: \{‘‘step’’: ‘‘\[A\] Caroline’’, ‘‘next’’: ‘‘1616ef6c\-b7ed\-4908\-bbf4\-cfa532591f0c’’\}\}\[SESSION: 3:31 pm on 23 August, 2023\]
2. 2\.Level 2:\{‘‘1616ef6c\-b7ed\-4908\-bbf4\-cfa532591f0c’’: \{‘‘step’’: ‘‘\[B\] discussing her identity’’, ‘‘next’’: ‘‘da0f6e17\-39f3\-460f\-848a\-eb3375327559’’\}\}\[SESSION: 2:31 pm on 17 July, 2023\]
3. 3\.Level 3:\{‘‘da0f6e17\-39f3\-460f\-848a\-eb3375327559’’: \{‘‘step’’: ‘‘What is \[A\]’s identity while \[B\]?’’\}\}\[SESSION: 1:36 pm on 3 July, 2023\]

Table 16:Full2×2×22\\times 2\\times 2tree structure for the Compositional StateTree sample \(conv\-26\)\.★\\bigstarmarks the target leaf\.Level 1Level 2 \(Event\)Level 3 \(Question / Answer\)\[A\] Caroline\[B\] discussing her identity \(correct\)★\\bigstarWhat is \[A\]’s identity while \[B\]?→\\rightarrowTransgender womanWhat career paths is \[A\] considering while \[B\]?→\\rightarrowPsychology, counseling certification\[B\] researching adoption agenciesWhat did \[A\] learn while \[B\]?→\\rightarrowAdoption agenciesWhen did \[A\] start \[B\]?→\\rightarrowresearching adoption agencies\[A\] Melanie\[B\] running a charity raceWhen did \[A\] participate in \[B\]?→\\rightarrowThe sunday before 25 May 2023What did \[B\] that \[A\] was part of raise awareness for?→\\rightarrowmental health\[B\] painting a sunsetWhat did \[A\] paint while \[B\]?→\\rightarrowsunsetWhat types of paintings has \[A\] done related to \[B\]?→\\rightarrowHorse, sunset, sunriseThe 14 edge records are distributed across 8 distinct sessions\.

## Appendix KQualitative Examples

### K\.1Cross\-Session Retrieval

The base model stops at the first matching session and returns a partial answer, whereas StateTree enumerates all relevant records distributed across sessions before aggregating a complete answer\.

Question \(LongMemEval\):“How many fish are there in total in both of my aquariums?” \(Ground truth:17\)

Qwen2\.5\-14B\-Instruct ResponseFrom previous conversations, the user mentioned having a 10\-gallon tank with a betta fish, Bubbles, and a 20\-gallon tank\. No specific number of fish in the 20\-gallon tank was mentioned, only types like schooling fish\. Therefore, the total number can only be estimated with the known fish in the 10\-gallon tank\.1\\boxed\{\\text\{1\}\}

StateTree\-14B ResponseFrom the conversation, the user mentioned having 10 neon tetras, 5 golden honey gouramis, and a small pleco catfish in their 20\-gallon tank\. They did not specify the number of fish in their other tank, but since the question is framed as if there is a known number in the other tank and based on previous context, we can infer they might be referring to their 10\-gallon tank which previously had a betta fish named Bubbles\. Assuming the 10\-gallon tank has only Bubbles and no other fish added, and the 20\-gallon tank has the mentioned 16 fish \(10 \+ 5 \+ 1\), the total number of fish would be 16 from the 20\-gallon tank and 1 from the 10\-gallon tank\.So, the total number of fish in both tanks is 10 neon tetras \+ 5 golden honey gouramis \+ 1 pleco catfish \+ 1 betta fish = 16 \+ 1 = 17 fish\.17\\boxed\{\\text\{17\}\}

Question \(LongMemEval\):“How many graduation ceremonies have I attended in the past three months?” \(Ground truth:3\)

Qwen2\.5\-14B\-Instruct ResponseThe user mentioned attending a niece’s preschool graduation ceremony on February 28th and a best friend’s master’s degree graduation ceremony a couple of weeks ago, which would be around March 10th to March 15th\. So, the user has attended two graduation ceremonies in the past three months\.2\\boxed\{\\text\{2\}\}

StateTree\-14B ResponseBased on the conversations, you have mentioned attending two graduation ceremonies in the past three months: 1\. Your colleague Alex’s graduation from a leadership development program at work a few weeks ago\. 2\. Your best friend Rachel’s master’s degree graduation ceremony last month from March 15th to 19th\. You also mentioned attending your little cousin Emma’s preschool graduation about two months ago, and your niece’s eighth grade graduation ceremony last month\.So, the total number of graduation ceremonies you have attended in the past three months is 3\.3\\boxed\{\\text\{3\}\}

### K\.2Multi\-Hop Reasoning

The base model fails to compose individual facts into the required inference, whereas StateTree chains scattered evidence into a coherent answer\.

Question \(LongMemEval\):“How old was I when Alex was born?” \(Ground truth:11\)

Qwen2\.5\-14B\-Instruct ResponseThe user mentioned they are considering mentoring a 21\-year\-old intern named Alex\. However, the user’s age was not directly mentioned in relation to Alex’s birth\. Based on the available context, the user recently turned 32 and is considering a career change\.32\\boxed\{\\text\{32\}\}

StateTree\-14B ResponseBased on the context provided, the user mentioned that they are 32 years old and are considering a career change for themselves\. They also mentioned that they are a mentor to Alex, an intern who is 21 years old\. However, the user did not directly state their age when Alex was born\. Given that Alex is 21 years old and the user is 32, the user was 32 \- 21 = 11 years old when Alex was born\.11\\boxed\{\\text\{11\}\}

Question \(LoCoMo\):“When did John resume playing drums in his adulthood?” \(Ground truth:February 2022\)

Qwen2\.5\-14B\-Instruct ResponseFrom the conversation on 27 March, 2022, John mentioned he started playing drums a month before the conversation\.a month ago\\boxed\{\\text\{a month ago\}\}

StateTree\-14B ResponseFrom the conversation on 27 March, 2022, John mentioned that he had been playing drums for a month and that he started playing again recently\. Since the conversation is dated 27 March, 2022, and John has been playing for a month by then, we can infer that he resumed playing drums sometime in February 2022\.February 2022\\boxed\{\\text\{February 2022\}\}

### K\.3Temporal Reasoning

The base model mis\-orders events using superficial lexical cues, whereas StateTree performs explicit chronological comparison via session timestamps\.

Question \(LoCoMo\):“Which activity did Sam resume in December 2023 after a long time?” \(Ground truth:hiking\)

Qwen2\.5\-14B\-Instruct ResponseReviewing the conversations, there’s no direct mention of Sam resuming any activity in December 2023\. However, the closest relevant information is from October onwards where Sam mentions starting a new diet and exercise routine, and discussing plans for healthier living\.exercise routine\\boxed\{\\text\{exercise routine\}\}

StateTree\-14B ResponseFrom the conversations, it is clear that Sam has been discussing and working on various activities such as dieting, exercising, and painting\. However, the specific date of December 2023 is not mentioned directly\. We need to infer from the context and timeline provided in the conversations\.The conversations span from 6 June 2023 to 25 October 2023\. Sam mentions starting a new diet and exercise routine and talks about his progress and setbacks\. He also mentions that he had a health scare and a doctor’s appointment that acted as a wake\-up call to prioritize his health\. Notably, Sam explicitly said “I love hiking, but it’s been ages since I’ve done it” and shared a childhood memory of hiking with his dad\. This “it’s been ages” directly corresponds to the question’s “after a long time\.” Furthermore, in October 2023, Sam and Evan were actively planning a hike together—Sam expressed excitement, shared a photo of hiking shoes, and said “Can’t wait to go on a hike with you\.” Given that Sam had a long\-standing interest in hiking but hadn’t done it in a very long time, and was making concrete plans to resume it, it is logical to conclude that the activity Sam resumed after a long time is hiking\.hiking\\boxed\{\\text\{hiking\}\}

Question \(LongMemEval\):“Which event did I attend first, the ‘Effective Time Management’ workshop or the ‘Data Analysis using Python’ webinar?” \(Ground truth:‘Data Analysis using Python’ webinar\)

Qwen2\.5\-14B\-Instruct ResponseThe user mentioned attending a ‘Effective Time Management’ workshop at the local community center last Saturday, and a ‘Data Analysis using Python’ webinar two months ago\. Based on the dates, the ‘Effective Time Management’ workshop was attended first\.Effective Time Management workshop\\boxed\{\\text\{Effective Time Management workshop\}\}

StateTree\-14B ResponseBased on the conversations, the user mentioned attending the ‘Effective Time Management’ workshop at the local community center on a specific date\. The ‘Data Analysis using Python’ webinar was mentioned as something they attended two months ago, which implies it was before the ‘Effective Time Management’ workshop\. Comparing the two: the webinar was attended two months prior to the workshop, placing it earlier on the timeline\.‘Data Analysis using Python’ webinar\\boxed\{\\text\{\`Data Analysis using Python' webinar\}\}

### K\.4Knowledge Update

The base model conflates old and new mentions, retrieving outdated values, whereas StateTree tracks the latest state by privileging more recent sessions\.

Question \(PersonaMem\):“I’m trying to decide whether to sign up for a structured painting class or just paint on my own time\. Any advice?” \(Ground truth:\(b\)\)

- \(a\)Considering you enjoy diving into new experiences and learning new things, a structured painting class might offer a fun and guided way to develop your skills\. You can benefit from expert advice and meet new people who share your passion\!
- \(b\)If you enjoy the freedom and creativity of spontaneous activities, you might find painting on your own time more fulfilling\. This allows you to focus on quality and explore your artistic interests without the constraints of a structured class\.
- \(c\)Painting on your own time gives you the chance to experiment with different styles and techniques at your own pace\. It can be a more flexible option if you’re looking for a stress\-relieving activity that fits your schedule\.
- \(d\)Both structured classes and painting on your own time have their merits\. A class can provide valuable feedback and a social environment\. If you appreciate structure, this might be the way to go\.

Qwen2\.5\-14B\-Instruct ResponseGiven the context of Alex’s recent experiences, it appears that Alex values both structured and unstructured creative endeavors\. However, Alex seems to prefer more casual and personal approaches, such as spontaneous movie nights and local film discussion groups, which suggest a preference for flexible and less stressful activities\. Therefore, option \(b\) or \(c\) might resonate more with Alex’s interests, but option \(c\) explicitly highlights the freedom and flexibility that aligns closely with Alex’s desire for a stress\-relieving activity that fits personal schedule\.\(c\)\\boxed\{\\text\{\(c\)\}\}

StateTree\-14B ResponseBased on the context of Alex Rivera’s preferences and experiences, it seems that Alex values both structured learning and personal freedom, but ultimately finds enjoyment and fulfillment in activities that are not overly stressful and allow for a more relaxed exploration of interests\. Alex has mentioned stepping back from organized events that felt too structured or overwhelming, such as readathons and film festivals, to find more personal and fulfilling ways to engage with literature and film\. However, Alex also expressed enthusiasm for organized events that foster community and learning, such as the local filmmaking workshop and the online film discussion group\.Given this balance, Alex might appreciate the guidance and feedback from a structured painting class but also the flexibility and personal expression that comes from painting independently\. However, the context leans slightly more towards the enjoyment of personal and less stressful activities, as Alex mentioned preferring spontaneous movie nights and smaller, more intimate film discussions over more structured events\.Considering this, the most appropriate advice would be one that aligns with the value Alex places on personal fulfillment and less pressure\. Option \(b\) emphasizes the freedom and creativity of painting on your own time, which seems to align well with Alex’s preference for not feeling constrained by a rigid structure\.\(b\)\\boxed\{\\text\{\(b\)\}\}

Question \(LongMemEval\):“How many new postcards have I added to my collection since I started collecting again?” \(Ground truth:25\)

Qwen2\.5\-14B\-Instruct ResponseReviewing the conversation, the user mentioned adding 17 new postcards since they started collecting again\.17\\boxed\{\\text\{17\}\}

StateTree\-14B ResponseFrom the conversation on 2023/05/20, the user mentioned they had added 17 new postcards since they started collecting again\. On 2023/11/10, the user mentioned they had added 8 more postcards to their collection\. However, the question specifically asks about the number of postcards added since they started collecting again, which initially was 17 postcards\. Adding the 8 new postcards, the total number of new postcards added since the start of their collection is 25\.The exact phrase from the conversation was “I’ve added 17 new ones since I started collecting again,” and later “I’ve added 25 new postcards to my collection since I started collecting again\.”Therefore, the total number of new postcards added since the start of the collection is 25\.25\\boxed\{\\text\{25\}\}

Question \(PersonaMem\):“I came across a platform that offers various finance webinars, and I signed up\.” \(Ground truth:\(b\)\)

- \(a\)I remember you mentioned not enjoying finance\-related webinars\. It might be refreshing to explore something outside your comfort zone like these\.
- \(b\)I remember you mentioned enjoying finance\-related webinars\. You might find them insightful for broadening your understanding of stock market strategies and financial planning\.
- \(c\)I remember you mentioned enjoying travel\-related webinars\. You might find them insightful for broadening your understanding of global cultures and geography\.
- \(d\)That’s interesting\! You must be excited to try out something new; how did you find that platform?

Qwen2\.5\-14B\-Instruct ResponseFrom the conversation, Alex mentioned not enjoying finance\-related webinars due to their complexity and rapid information sharing, which can be overwhelming\. However, since then, Alex has shown an increasing interest in financial literacy and has been exploring finance\-related topics through various means such as reading, discussions, and personal projects\. Given Alex’s renewed engagement with finance, option \(a\) doesn’t seem to fit as Alex is not looking to explore something outside their current interest\. Option \(c\) is irrelevant since Alex has not expressed interest in travel\-related webinars\. Between \(b\) and \(d\), \(d\) seems more appropriate as it is more open\-ended and does not assume Alex enjoys the webinars but rather acknowledges the newness of the platform and seeks feedback\.\(d\)\\boxed\{\\text\{\(d\)\}\}

StateTree\-14B ResponseBased on the conversation, Alex mentioned that they had attended finance\-related webinars and found them to be beneficial, even if some of the content was challenging\. They expressed a positive attitude towards webinars in general, especially those related to finance\. Therefore, the most appropriate response would be option \(b\), which aligns with Alex’s past experiences and interests\.\(b\)\\boxed\{\\text\{\(b\)\}\}