The Context Gathering Decision Process: A POMDP Framework for Agentic Search
Authors: Chinmaya Kausik, Adith Swaminathan, Nathan Kallus
Summary
The authors formalize the problem of an LLM agent searching through a large environment (like a codebase or database) as a "Context Gathering Decision Process" (CGDP), a special kind of partially observable Markov decision process where the agent must iteratively gather information to build up the context it needs. They show that LLMs implicitly do approximate Thompson Sampling in this setting, then propose two plug-and-play improvements: a persistent belief state based on logical predicates that preserves multi-hop reasoning while bounding context size, and a programmatic check that stops unproductive search without giving up too early. These improve multi-hop reasoning by up to 11.4% and save up to 39% of tokens across four methods and three question-answering domains.
Main takeaways:
- LLM agents searching large environments (codebases, databases) can degrade into lossy memory states, causing repetitive loops and premature stopping
- Context Gathering Decision Process (CGDP) formalizes this as a POMDP where the agent adaptively refines its belief to isolate task-relevant information
- Persistent predicate-based belief state bounds context while preserving multi-hop reasoning, improving performance by up to 11.4%
- Programmatic exhaustion gate halts unproductive search without premature stopping, saving up to 39% of tokens with no performance loss
- Framing the agent loop as a CGDP enables modular, non-interfering improvements to search harnesses
Relevance
Not directly related to my persona installation work, but potentially useful if I ever need to study how personas behave during multi-turn search or information-gathering tasks. The idea of a persistent belief state that prevents lossy memory could relate to how persona-specific information is maintained across a long conversation.
Abstract
arXiv:2605.07042v1 Announce Type: new Abstract: 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.