# StateTree: Enhancing Long-Term Dialogue Reasoning via Reinforcement Learning

arXiv: https://arxiv.org/abs/2609.38809 · HTML: https://mlsanity.com/paper/2609.38809/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 37 of its 48 references that are in the map.
- First posted on arXiv 30 Sep 2026.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 30 of 37)

- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [Measuring Massive Multitask Language Understanding](https://mlsanity.com/paper/2009.03300/) (2020)
- [GPT-4o System Card](https://mlsanity.com/paper/2410.21276/) (2024)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering](https://mlsanity.com/paper/1809.09600/) (2018)
- [Lost in the Middle: How Language Models Use Long Contexts](https://mlsanity.com/paper/2307.03172/) (2023)
- [DAPO: An Open-Source LLM Reinforcement Learning System at Scale](https://mlsanity.com/paper/2503.14476/) (2025)
- [Qwen2 Technical Report](https://mlsanity.com/paper/2407.10671/) (2024)
- [Constructing A Multi-hop QA Dataset for Comprehensive Evaluation of Reasoning Steps](https://mlsanity.com/paper/2011.01060/) (2020)
- [Instruction-Following Evaluation for Large Language Models](https://mlsanity.com/paper/2311.07911/) (2023)
- [Kimi k1.5: Scaling Reinforcement Learning with LLMs](https://mlsanity.com/paper/2501.12599/) (2025)
- [Evaluating Very Long-Term Conversational Memory of LLM Agents](https://mlsanity.com/paper/2402.17753/) (2024)
- [LongMemEval: Benchmarking Chat Assistants on Long-Term Interactive Memory](https://mlsanity.com/paper/2410.10813/) (2024)
- [SFT Memorizes, RL Generalizes: A Comparative Study of Foundation Model Post-training](https://mlsanity.com/paper/2501.17161/) (2025)
- [YaRN: Efficient Context Window Extension of Large Language Models](https://mlsanity.com/paper/2309.00071/) (2023)
- [MemoryBank: Enhancing Large Language Models with Long-Term Memory](https://mlsanity.com/paper/2305.10250/) (2023)
- [LLMs Get Lost In Multi-Turn Conversation](https://mlsanity.com/paper/2505.06120/) (2025)
- [TravelPlanner: A Benchmark for Real-World Planning with Language Agents](https://mlsanity.com/paper/2402.01622/) (2024)
- [MemAgent: Reshaping Long-Context LLM with Multi-Conv RL-based Memory Agent](https://mlsanity.com/paper/2507.02259/) (2025)
- [ProRL: Prolonged Reinforcement Learning Expands Reasoning Boundaries in Large Language Models](https://mlsanity.com/paper/2505.24864/) (2025)
- [LightMem: Lightweight and Efficient Memory-Augmented Generation](https://mlsanity.com/paper/2510.18866/) (2025)
- [Know Me, Respond to Me: Benchmarking LLMs for Dynamic User Profiling and Personalized Responses at Scale](https://mlsanity.com/paper/2504.14225/) (2025)
- [APIGen-MT: Agentic Pipeline for Multi-Turn Data Generation via Simulated Agent-Human Interplay](https://mlsanity.com/paper/2504.03601/) (2025)
- [MiniMax-01: Scaling Foundation Models with Lightning Attention](https://mlsanity.com/paper/2501.08313/) (2025)
- [Pearl: Personalizing Large Language Model Writing Assistants with Generation-Calibrated Retrievers](https://mlsanity.com/paper/2311.09180/) (2023)
- [Are Large Language Models Capable of Generating Human-Level Narratives?](https://mlsanity.com/paper/2407.13248/) (2024)
- [LongReason: A Synthetic Long-Context Reasoning Benchmark via Context Expansion](https://mlsanity.com/paper/2501.15089/) (2025)
- [QwenLong-L1: Towards Long-Context Large Reasoning Models with Reinforcement Learning](https://mlsanity.com/paper/2505.17667/) (2025)
- [Large Language Models Can Self-Improve in Long-context Reasoning](https://mlsanity.com/paper/2411.08147/) (2024)

## Abstract (arXiv)

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%).