# The Context Gathering Decision Process: A POMDP Framework for Agentic Search

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Placed in Agent memory systems, one of 16 directions in LLM agents and tool use.
- Builds on 40 of its 46 references that are in the map.
- First posted on arXiv 7 May 2026.

## Placed in

- LLM agents and tool use / [Agent memory systems](https://mlsanity.com/agents/agent-memory-systems/)

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

- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Generative Agents: Interactive Simulacra of Human Behavior](https://mlsanity.com/paper/2304.03442/) (2023)
- [Lost in the Middle: How Language Models Use Long Contexts](https://mlsanity.com/paper/2307.03172/) (2023)
- [Self-RAG: Learning to Retrieve, Generate, and Critique through Self-Reflection](https://mlsanity.com/paper/2310.11511/) (2023)
- [SWE-agent: Agent-Computer Interfaces Enable Automated Software Engineering](https://mlsanity.com/paper/2405.15793/) (2024)
- [From Local to Global: A Graph RAG Approach to Query-Focused Summarization](https://mlsanity.com/paper/2404.16130/) (2024)
- [Search-R1: Training LLMs to Reason and Leverage Search Engines with Reinforcement Learning](https://mlsanity.com/paper/2503.09516/) (2025)
- [MemGPT: Towards LLMs as Operating Systems](https://mlsanity.com/paper/2310.08560/) (2023)
- [A-MEM: Agentic Memory for LLM Agents](https://mlsanity.com/paper/2502.12110/) (2025)
- [Large Language Models Cannot Self-Correct Reasoning Yet](https://mlsanity.com/paper/2310.01798/) (2023)
- [Interleaving Retrieval with Chain-of-Thought Reasoning for Knowledge-Intensive Multi-Step Questions](https://mlsanity.com/paper/2212.10509/) (2022)
- [MuSiQue: Multihop Questions via Single-hop Question Composition](https://mlsanity.com/paper/2108.00573/) (2021)
- [Evaluating Very Long-Term Conversational Memory of LLM Agents](https://mlsanity.com/paper/2402.17753/) (2024)
- [Active Retrieval Augmented Generation](https://mlsanity.com/paper/2305.06983/) (2023)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Search-o1: Agentic Search-Enhanced Large Reasoning Models](https://mlsanity.com/paper/2501.05366/) (2025)
- [LLMs Get Lost In Multi-Turn Conversation](https://mlsanity.com/paper/2505.06120/) (2025)
- [Enhancing Retrieval-Augmented Large Language Models with Iterative Retrieval-Generation Synergy](https://mlsanity.com/paper/2305.15294/) (2023)
- [WebThinker: Empowering Large Reasoning Models with Deep Research Capability](https://mlsanity.com/paper/2504.21776/) (2025)
- [DeepResearcher: Scaling Deep Research via Reinforcement Learning in Real-world Environments](https://mlsanity.com/paper/2504.03160/) (2025)
- [HippoRAG: Neurobiologically Inspired Long-Term Memory for Large Language Models](https://mlsanity.com/paper/2405.14831/) (2024)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [LooGLE: Can Long-Context Language Models Understand Long Contexts?](https://mlsanity.com/paper/2311.04939/) (2023)
- [Corrective Retrieval Augmented Generation](https://mlsanity.com/paper/2401.15884/) (2024)
- [Don't Hallucinate, Abstain: Identifying LLM Knowledge Gaps via Multi-LLM Collaboration](https://mlsanity.com/paper/2402.00367/) (2024)
- [Self-contradictory Hallucinations of Large Language Models: Evaluation, Detection and Mitigation](https://mlsanity.com/paper/2305.15852/) (2023)
- [Long-Context LLMs Meet RAG: Overcoming Challenges for Long Inputs in RAG](https://mlsanity.com/paper/2410.05983/) (2024)
- [Simple Bayesian Algorithms for Best Arm Identification](https://mlsanity.com/paper/1602.08448/) (2016)

## Built on by (most cited first, 6 of 6)

- [DART-SD: Diamond-topology Aware Retrieval and Tuning for Self-Distillation of Multi-Turn Tool-Calling Agents](https://mlsanity.com/paper/2608.18524/) (2026)
- [From Simple QA to Deep Research: A Verifiable Benchmark Constructed through Iterative Task Evolution](https://mlsanity.com/paper/2608.02163/) (2026)
- [MNIST-PRO: MNIST is Back as a Partially Observable World for AI Agents](https://mlsanity.com/paper/2608.31022/) (2026)
- [Beyond Memory: Harnessing Long-Horizon Agents with Explicit Belief States](https://mlsanity.com/paper/2610.01415/) (2026)
- [Learning What to Investigate Next: Meta-Reasoning for Long-Horizon Research Agents](https://mlsanity.com/paper/2610.02525/) (2026)
- [Programmatic Search Agents: Extending Agentic Search Beyond Query Reformulation](https://mlsanity.com/paper/2610.06689/) (2026)

## Abstract (arXiv)

Large Language Model (LLM) agents are deployed in complex environments -- such as massive codebases, enterprise databases, and conversational histories -- where the relevant state far exceeds their context windows. To navigate these spaces, an agent must iteratively explore the environment to find relevant information. However, without explicit infrastructure, an agent's working memory can degrade into lossy representations of the search state, resulting in redundant work (e.g. repetitive looping) and premature stopping. In this work, we formalize this challenge as the Context Gathering Decision Process (CGDP), a specialized Partially Observable Markov Decision Process, where an agent's objective is to adaptively refine its belief state to isolate the necessary information for a task. We model an LLM's behavior as approximate Thompson Sampling within this CGDP, and introduce a predicate-based method that decomposes an LLM's implicit search into explicit and modular operations. We then derive two plug-and-play interventions for iterative LLM agents: a persistent, predicate-based belief state that bounds context while preserving multi-hop reasoning, and a programmatic exhaustion gate that halts unproductive search without premature stopping. Across four methods and three question-answering domains, we empirically validate that replacing an LLM's implicit state with our CGDP-motivated belief state improves multi-hop reasoning by up to 11.4%; while the modular programmatic exhaustion detection saves up to 39% of tokens without any degradation in agent performance. Ultimately, we argue that framing the LLM agent loop as a CGDP can guide the design of modular, non-interfering improvements to agentic search harnesses.