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