Stack-Based Context Management for Recursive Dialogue

86 concepts64 papers

When we talk to each other, we rarely speak in a straight line. A simple conversation about booking a train ticket can easily detour into a clarification about departure times, a brief negotiation over ticket prices, or an outright interruption when someone drops a coffee cup. Yet, as human speakers, we navigate these conversational detours effortlessly. We instinctively know when a side-discussion has concluded and exactly where to pick up the original thread.

For computational dialogue systems, however, this non-linear behavior is a major hurdle. If a system treats conversation as a flat, chronological log of utterances, an interruption can permanently derail its long-term goals.

To solve this, researchers developed a powerful structural intuition: dialogue is not a flat list; it is a stack. By modeling conversational context using hierarchical, Last-In, First-Out (LIFO) data structures, systems can dynamically isolate, pause, and resume conversational threads.

The Core Intuition: Focus Spaces and the LIFO Stack

The foundational challenge of dialogue management is tracking what is currently relevant—a concept known as the attentional state. In a flat history, resolving a pronoun like "it" requires searching backward through every single mentioned entity. If the user temporarily changed the subject two turns ago, a linear search will often pull the wrong reference.

To fix this, early computational frameworks shifted from linear histories to hierarchical structures. In Levels of Complexity in Discourse for Anaphora Disambiguation and Speech Act Interpretation, C. Bullwinkle proposed a stack-based mechanism to track primary topics and temporary sub-topics. When a user introduces a sub-discussion, the system pushes a new topic onto the stack. When that sub-discussion concludes, the system pops the stack, instantly restoring the previous focus and ensuring continuity.

[ Push Sub-Topic ]  -->  | Sub-Topic Context  |  (Active Focus)
                         |--------------------|
[ Pop on Completion ]    | Main Topic Context |  (Suspended Focus)
                         +--------------------+

This mechanism was formalized in the seminal work of Barbara J. Grosz and Candace L. Sidner. In Discourse Structure and the Proper Treatment of Interruptions, Grosz et al. introduced the concept of focus spaces. Each discourse segment corresponds to a discrete focus space containing only the entities and properties salient to that specific sub-task.

By organizing these spaces into a LIFO stack, the system achieves two critical capabilities:

  1. Nested Isolation: An interruption pushes a new focus space onto the stack, hiding the parent context so it cannot be corrupted by irrelevant intermediate chatter.
  2. Seamless Return: Once the interruption is resolved, its focus space is popped off, and the previous attentional state becomes active again.

This structural approach explains why systems can resolve highly ambiguous or incomplete utterances. For instance, Diane J. Litman demonstrated in Linguistic Coherence: a Plan-Based Alternative and Understanding Plan Ellipsis that tracking active and suspended dialogue contexts via a plan stack allows a system to resolve fragmented phrases (like "How about Wednesday?") by applying coherence heuristics directly to the most relevant plan on top of the stack.

Handling Nested Uncertainty and Obligations

As dialogue models evolved, researchers realized that topic shifts aren't just driven by task transitions; they are also driven by social obligations and cognitive friction.

When an agent makes a statement and the user disagrees, the primary task is suspended. The conversation enters a negotiation subdialogue to resolve the disagreement. In Modeling Negotiation Subdialogues, Lambert et al. showed that these interactions are fundamentally recursive. If the agent provides evidence to back up its claim, and the user challenges that evidence, a second negotiation subdialogue is spawned inside the first one.

Main Task: Book Flight
  └── Subdialogue 1: Negotiate Price
        └── Subdialogue 2: Validate Discount Eligibility (Nested)

Managing this requires a recursive model of dialogue. As Chu-Carroll et al. demonstrated in Response Generation in Collaborative Negotiation and Generating Information-Sharing Subdialogues in Expert-User Consultation, treating the rejection of evidence as a new proposal within a nested structure allows agents to handle layers of disagreement systematically. The system recursively resolves the deepest conflict first, popping back up to the primary negotiation only when all prerequisite dependencies are satisfied.

Similarly, conversation incurs social debts. In Discourse Obligations in Dialogue Processing, Traum et al. modeled pending conversational requirements (like answering a question or acknowledging a statement) as a stack structure. This ensures that the most recent discourse obligations are prioritized first, matching the natural conversational repair strategies humans use every day.

Modern Relevance: Context Hygiene in LLM Agents

While early work relied on hand-crafted grammars and finite-state transducers, the core intuition of hierarchical context isolation has become vital for modern Large Language Model (LLM) agents.

When multiple LLM agents collaborate to solve a complex problem, a flat, shared chat history quickly leads to "context fatigue." The context window becomes cluttered with intermediate brainstorming, causing the primary orchestrator to lose track of the high-level goal.

To solve this, modern multi-agent frameworks return directly to the principles of nested context isolation. In Adaptive In-conversation Team Building for Language Model Agents, Song et al. introduced a mechanism that confines sub-agent interactions to isolated, nested dialogue threads.

[Primary Orchestrator Context]
       │
       ├──> [Isolated Thread: Sub-Agent Brainstorming] (Hidden from Main Context)
       │          └── Detailed code iterations & logs
       │
[Summary Returned] ──> Main Context stays clean and focused.

By isolating detailed sub-agent brainstorming within nested sessions, the primary orchestrator only receives a high-level summary once the sub-task concludes. This prevents performance degradation caused by long, noisy context windows—a direct modern application of the focus spaces proposed decades earlier.

Furthermore, this hierarchical approach is being built directly into modern programming paradigms for AI. The framework introduced in APPL: A Prompt Programming Language for Harmonious Integration of Programs and Large Language Model Prompts uses nested function calls to manage prompt history. By allowing developers to explicitly define inheritance modes—such as creating a clean slate, copying the current context, or maintaining a isolated reference—it provides a programmatic way to enforce stack-based state management in complex, multi-step LLM workflows.

Why the Idea Works

Stack-based and hierarchical context management works because it aligns the computational representation of a conversation with its underlying cognitive structure. Human communication is goal-driven, and goals have prerequisites. By treating dialogue as a dynamic stack of focus spaces, subdialogues, or isolated threads, conversational systems gain three timeless advantages:

  • Search Efficiency: Pronoun resolution and intent interpretation are restricted to the active focus space on top of the stack, eliminating the need to search through irrelevant historical turns.
  • Resilience to Disruption: Interruptions do not destroy the context of the primary task; they merely suspend it until the top of the stack is cleared.
  • Context Hygiene: Irrelevant low-level chatter is isolated within nested structures, keeping the high-level context clean, coherent, and focused on long-term objectives.

Key Foundational Work

Levels of Complexity in Discourse for Anaphora Disambiguation and Speech Act Interpretation (1977) — contributed 2 concept elements to this direction.
Modelling Simple Dialogs (1977) — contributed 2 concept elements to this direction.
Levels of Complexity in Discourse for Anaphora Disambiguation and Speech Act Interpretation (1977) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_recursive_subdialogue_management_bfa828c3,
  title = {recursive subdialogue management},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/recursive-subdialogue-management/rdr_bfa828c3e1cf4015be65d06c477e645b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_recursive_subdialogue_management_bfa828c3_v1,
  title = {recursive subdialogue management},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/recursive-subdialogue-management/rdr_bfa828c3e1cf4015be65d06c477e645b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}

See something wrong? Report a mistake