DYCP: Dynamic Context Pruning for Long-Form Dialogue with LLMs

1. Problem Statement

Large Language Models (LLMs) are increasingly deployed in long-form dialogue systems where conversations span hundreds of turns with frequent topic shifts. While modern LLMs support extended context windows (e.g., 128k to 1M tokens), utilizing the full dialogue history for every turn introduces significant practical challenges:

• Inference Cost & Latency: Processing massive context windows increases GPU resource usage, API costs, and response latency (time to first token).
• The "Needle-in-a-Haystack" Problem: As context grows, models struggle to identify relevant information buried within irrelevant dialogue, often leading to hallucinations or ignoring critical details.
• Limitations of Existing Solutions:
  • Summarization: Risks omitting key details necessary for the current turn.
  • Turn-level Retrieval: Efficient but often disrupts discourse coherence by ignoring dependencies between consecutive turns.
  • Segment-level Retrieval (Pre-segmentation): Existing methods (e.g., MemoChat, SeCom) rely on offline pre-segmentation (grouping turns into topics before the query arrives). This assumes fixed topic boundaries, which may not align with the current user's intent, and often requires additional LLM calls for segmentation, increasing cost.

2. Methodology: DYCP

The authors propose DYCP (Dynamic Context Pruning), a lightweight, query-dependent context management method that operates outside the LLM. It dynamically identifies and retrieves relevant dialogue segments at inference time without pre-segmentation or additional LLM calls.

Core Components:

1. Turn-Level Embedding:
   • Dialogue history $H$ is processed turn-by-turn. Each turn $k$ (user query $q_k$ + agent response $a_k$) is concatenated and encoded into a vector embedding using a bi-encoder retriever $B$.
   • These embeddings are stored incrementally.
2. Relevance Scoring:
   • For the current user query $q_n$, an embedding is generated and compared against all previous turn embeddings to produce a relevance score sequence $S$.
3. KadaneDial Algorithm:
   • The core innovation is KadaneDial, an adaptation of the classic Kadane's algorithm (used for finding the maximum subarray sum).
   • Mechanism: The relevance scores $S$ are treated as a 1D signal. The algorithm standardizes scores (z-score) and applies a gain threshold ($\tau$) to calculate "excess" gain.
   • Dynamic Span Selection: It iteratively identifies consecutive spans of turns where the cumulative relevance gain remains high. Unlike fixed top-$k$ retrieval, it can select multiple non-contiguous segments (e.g., Turns 7–15 and Turns 40–45) if they both show sustained relevance to the current query.
   • Continuity Preservation: Selected spans are concatenated in their original chronological order to maintain dialogue flow.
4. Input Construction:
   • The pruned history $H'$ (selected turns) is prepended to the current query $q_n$ and fed to the LLM for generation.

3. Key Contributions

• Novel Algorithm: Introduction of KadaneDial, a linear-time method for dynamically selecting coherent, query-relevant dialogue segments without pre-segmentation.
• Cost-Efficiency: The method requires zero offline LLM calls and only a single inference-time call per query, significantly reducing latency and API costs compared to methods requiring memory construction or refinement.
• Comprehensive Evaluation: A systematic comparison against six baselines (No Context, Full Context, MemoChat, SCM4LLMs, SeCom, CondMem) across three long-form benchmarks (LoCoMo, MT-Bench+, SCM4LLMs) and five LLM backends (GPT-4o, Claude 3.7/4.0, GPT-4o mini, GPT-4.1).
• Insight into Long-Context Behavior: Analysis revealing that even with massive context windows, models exhibit position bias (recency bias) and struggle with long-range dependencies, making selective pruning vital.

4. Experimental Results

The study evaluated DYCP across three benchmarks with varying dialogue lengths (up to 300+ turns).

• Answer Quality:
  • DYCP consistently matched or outperformed the "Full Context" baseline in answer quality (measured by GPT4Score, Exact Match, and ROUGE) across most models and datasets.
  • On LoCoMo (longest dialogues), DYCP achieved a GPT4Score of 83.27 vs. Full Context's 75.13 on GPT-4o, demonstrating that pruning helps mitigate the "needle-in-a-haystack" issue.
  • Even with newer models like GPT-4.1 (which handles long contexts better), DYCP maintained comparable quality while being significantly faster.
• Latency & Efficiency:
  • Latency: DYCP reduced first-token latency by approximately 2x to 3x compared to Full Context (e.g., 0.97s vs. 2.41s on GPT-4.1 for LoCoMo).
  • Token Usage: DYCP reduced input context tokens by roughly 80% (e.g., from ~25k tokens to ~5k tokens on LoCoMo) while maintaining performance.
• Retrieval Accuracy:
  • DYCP achieved higher Recall@k and Hit@k compared to segment-level baselines (SeCom, SCM4LLMs), indicating better alignment between the selected context and the query.
  • The study found that high recall (ensuring relevant info is included, even if some noise is present) is more critical for answer quality than high precision.
• Open-Source Models: DYCP generalized well to open-source models (Qwen2.5-7B, Mistral-Nemo), outperforming Full Context and CondMem in both quality and latency.

5. Significance and Implications

• Practical Deployment: DYCP offers a scalable, LLM-agnostic strategy for managing long conversations in real-world applications where inference cost and latency are critical constraints.
• Rethinking Context Limits: The paper challenges the assumption that "larger context windows" automatically solve long-dialogue problems. It suggests that effective working memory in LLMs is often limited by attention mechanisms and position bias, making intelligent pruning more effective than brute-force context expansion.
• Dynamic vs. Static: The results highlight that query-dependent segmentation (DYCP) is superior to offline pre-segmentation because dialogue topics are fluid and depend on the current user intent.
• Trade-off Management: The method provides a principled way to balance Recall (not missing info) and Efficiency (latency/cost), showing that adaptive span selection yields better results than fixed top-$k$ approaches.

Conclusion: DYCP demonstrates that for long-form dialogue, dynamically pruning context based on real-time relevance is not only more efficient but often leads to higher quality responses than feeding the entire history to the model, even for state-of-the-art LLMs.