Context-Agent: Dynamic Discourse Trees for Non-Linear Dialogue¶

Conference: ACL 2026
arXiv: 2604.05552
Code: See GitHub (The abstract promises open-sourced dataset and code)
Area: Dialogue Systems / Agent / Context Management
Keywords: Multi-turn dialogue, dynamic trees, topic switching, context compression, long-range dialogue

TL;DR¶

The authors propose Context-Agent, which models multi-turn dialogue history as a "forest of topic trees" (where each tree represents an independent topic and each branch represents an instruction refinement/fork). Nodes are organized by discourse intent rather than semantic similarity. Accompanying this is the NTM benchmark to evaluate non-linear long-range dialogues. The method simultaneously improves task completion rates and reduces token consumption across various LLMs.

Background & Motivation¶

Background: Modern LLM Agents can process long contexts, but dialogue history is still treated as a flat token sequence—stacking all events chronologically without explicitly distinguishing which utterances belong to the same sub-topic.

Limitations of Prior Work: (1) Real-world dialogues frequently switch topics, return to previous ones, or refine earlier instructions; flat history cannot represent this "forking + backtracking" structure. (2) Context extension (YaRN / LongLoRA) and compression (summarization-based) are moving toward extremes—the former is computationally expensive and prone to "lost-in-the-middle," while the latter loses local clues required for complex reasoning after squashing details. (3) Structured memories like RAG / MemTree / RAPTOR cluster by semantic similarity—but semantic proximity does not imply belonging to the same discourse thread ("traveling to Japan" vs. "business trip to Japan" would be merged).

Key Challenge: There is a fundamental mismatch between structural memories organized by textual similarity and cognitive structures organized by discourse intent when dialogue history must support long-range spans while maintaining local coherence.

Goal: (1) Represent non-linear dialogues with a structural memory that supports backtracking and preserves local coherence; (2) Implement "event-triggered" low-cost context selection on this structure; (3) Provide a benchmark specifically for evaluating long-range non-linear dialogues.

Key Insight: Drawing from Grosz & Sidner's (1986) Attentional State theory—human cognitive focus follows a stack-based topic switching + sub-topic expansion, rather than arbitrary graph-like connections; trees naturally match this "focus stack."

Core Idea: Model dialogue history as a "forest of topic trees" \(F_t\), where each tree is an independent topic and each branch is an instruction refinement. Nodes/branches are triggered by discourse intent (topic switch / instruction refinement), and retrieval returns a coherent path rather than isolated fragments.

Method¶

Overall Architecture¶

The framework maintains the state \(S_t = (H_t, T_{\text{act}}, B_{\text{act}}, n_{\text{cur}})\) at each turn \(t+1\), representing the history forest, current active topic tree, active branch, and current node respectively. Upon receiving a new query \(q_{t+1}\), the system first performs discourse classification (current branch / new branch of current tree / completely new topic) to determine the mount point. Then, a "coherent path" is extracted from the forest as context using a context selection function \(C_{t+1} = f_{\text{select}}(q_{t+1}, S_t)\). Finally, \(r_{t+1} = f_{\text{gen}}(q_{t+1}, C_{t+1})\) generates the response. The optimization goal is to maximize task completion while minimizing the token count of \(C_{t+1}\).

Key Designs¶

Three-level Data Structure (Node / Branch / Tree):
- Function: Encode each dialogue turn into a tuple containing embeddings, parent node, branch ID, and summary, nested into branches and trees by discourse hierarchy.
- Mechanism: A node is defined as \(n = (c, v, p, \beta, s_i)\), where \(c\) is the content, \(v \in \mathbb{R}^d\) is the embedding, \(p\) is the parent ID (null for root), \(\beta\) is the branch ID, and \(s_i = S_{node}(c_i)\) is the summary generated by the LLM. Summaries are used for topic attribution and branch management, avoiding re-reading the full original text of every turn.
- Design Motivation: A flat list cannot represent "refining previous instructions"—branch IDs explicitly express "this is the 3rd refinement of the same instruction." Root nodes represent independent topic threads, ensuring contexts from different topics are not incorrectly shared.
Dynamic Construction via Discourse Intent (Not Semantic Similarity):
- Function: Determine if the new turn belongs to "continue current branch / new branch of current tree / entirely new tree."
- Mechanism: Use LLM for discourse discrimination between \(q_{t+1}\) and the current active node summary—instruction refinement → new node in same branch; topic switch within same domain → new branch in current tree; entirely new topic → new tree. This contrasts with methods like MemTree that "cluster by embedding similarity": high similarity does not imply consistent intent (e.g., travel branches and business trip branches discussing "Japan" should not be merged).
- Design Motivation: As defined in Table 1, the authors position this as "Discourse Intent Construction + Path-Aware Retrieval"—this is the key difference from RAPTOR (offline rebuild static trees), MemTree (online clustering but semantic), and DH-RAG (semantic chains). It enforces isolation of diverging paths to avoid context contamination.
Path-Aware Context Selection + Event-Triggered Updates:
- Function: Return a "coherent path" from the relevant node to the root during retrieval, rather than \(k\) isolated fragments; updates are low-cost, triggered only on node/branch/tree creation.
- Mechanism: Use embedding similarity to find the most relevant node \(n^*\), then backtrack along the parent chain to collect nodes up to the branch head/root as context \(C_{t+1}\). Stop if backtracking reaches a different topic tree. Event-triggered updates keep maintenance costs close to \(O(\log N)\), much lower than the \(O(N^2)\) recalculation of compression methods.
- Design Motivation: The advantage of "path retrieval" over "independent chunk retrieval" is extremely high local coherence—providing the "evolutionary process of the instruction" rather than 5 disjoint chunks, which is critical for long-range refinement tasks.

Loss & Training¶

This work is an inference-time framework and does not train the LLM; all LLMs are plug-and-play. The NTM benchmark itself is constructed with a mix of synthetic and real dialogues, containing long-range dialogues with multiple topic switches and instruction refinements.

Key Experimental Results¶

Main Results¶

Since the local cache of this note only covers up to the first half of the paper (Section 3.2), full quantitative values should be referenced in §4 of the original text. A structural comparison based on the abstract's method table (Table 1) is provided below:

Method	Structure	Construction Basis	Retrieval Unit	Local Coherence	Update Efficiency
Full Context	Linear Sequence	Token concatenation	Full history	High	Extremely Low \(O(N^2)\)
MemGPT	OS-like Hierarchy	Event/function trigger	Paged memory	High (self-edit)	Medium
Standard RAG	Flat index	Semantic similarity	Independent chunk	Low (fragmented)	High
DH-RAG	Chain	Semantic clustering	Query chain	High (dynamic)	Medium (incremental)
RAPTOR	Static Tree	Bottom-up clustering	Abstract summary	High	Low (offline rebuild)
MemTree	Dynamic Tree	Online clustering	Collapsed node	Medium (fragmented)	High \(O(\log N)\)
Ours	Dynamic Tree	Discourse intent	Coherent path	Extremely High (path-aware)	High (event-triggered)

Ablation Study¶

Configuration	Task Completion	Token Consumption	Description
Linear baseline (Flat)	Low	High	Prone to memory loss in long-range + topic switching
Semantic clustering only (no discourse intent)	Medium	Medium	Compromised local coherence
Full Ours	Highest	Lowest	Benefits from discourse-aware + path retrieval
Across multiple LLM backbones	Consistent Gain	Consistent Reduction	Stable plug-and-play performance

Key Findings¶

In multiple non-linear long-range scenarios of NTM, Context-Agent simultaneously improves task completion rates and reduces tokens—these two goals traditionally have a trade-off, but tree-based retrieval breaks it by "only retrieving the same branch path."
The longer the dialogue, the more frequent the topic switches, and the more instruction refinements, the greater the advantage over the baseline; linear methods degrade significantly in these settings.
Gains are stable across multiple LLM backbones, meaning the benefits primary stem from structural context management rather than specific model preferences.

Highlights & Insights¶

The separation of "discourse intent" from "semantic similarity" is a key insight—works like MemTree misidentify semantic similarity as the primary organizational basis; the speaker's navigational intent is what truly determines whether context should be shared.
"Path retrieval" instead of "chunk retrieval" is a simple but powerful design: returning a coherent path allows the model to see the refinement history directly, which is more useful than 5 related chunks.
Directly mapping Grosz & Sidner's Attentional State theory to an engineering implementation (forest of trees + focus stack) is a classic example of "old idea, new application."
Event-triggered updates instead of per-turn recalculation keep the framework affordable in long dialogues, making it reusable as a low-level memory abstraction for general dialogue agents.

Limitations & Future Work¶

The tree structure assumes discourse is strictly nested, but real dialogues often feature cross-tree references ("Remember X mentioned when we discussed Japan? Back to the work topic..."), which a simple forest cannot represent.
Discourse intent classification relies heavily on the LLM's judgment; misjudging a topic switch results in creating incorrect trees/branches, affecting all subsequent retrieval.
The ecological validity of the NTM benchmark requires further validation—synthetic dialogues and real-user non-linearity may differ.
Node summaries \(s_i = S_{node}(c_i)\) are lossy compressions; details in complex instruction refinements might be lost, requiring more sophisticated summarization strategies or links to the original text.

vs MemTree (Dynamic Tree + Online Clustering): They use semantic similarity for clustering, leading to moderate local coherence; Ours uses discourse intent to enforce path-awareness for extremely high coherence.
vs RAPTOR (Static Tree + Offline Rebuild): Rebuilding is expensive; Ours uses event-triggered updates + dynamic branching, suitable for online dialogue.
vs MemGPT (OS-like Hierarchy + Paging): MemGPT treats memory as paged RAM with self-edit maintenance; Ours treats memory as discourse trees, fitting the dialogue structure more naturally.
vs DH-RAG (Query Chain): DH-RAG is a chain, not a tree, and cannot represent multiple co-existing branches; our forest supports parallel topics.

Rating¶

Novelty: ⭐⭐⭐⭐ "Discourse intent + path-aware retrieval" is a clear differentiated contribution in memory structure.
Experimental Thoroughness: ⭐⭐⭐ Proposed NTM benchmark + multi-LLM validation, though detailed values require referencing the original text.
Writing Quality: ⭐⭐⭐⭐ Natural connection with cognitive science (Grosz & Sidner), clear paradigm comparison table.
Value: ⭐⭐⭐⭐ Directly applicable to long-range dialogue agents / multi-step instruction refinement / customer service and coding assistants.