MemSeeker: Query-Time Memory Construction

Memory for LLM agents often relies on prebuilt semantic stores or query-time search over raw histories. Prebuilt stores incur upfront construction costs before query needs are known, while stateless search agents repeatedly spend effort locating and synthesizing evidence that earlier queries have already uncovered. To address these limitations, we define Query-Time Memory Construction (QTMC) as a memory construction strategy that starts with an empty store and incrementally constructs persistent memory from completed query trajectories for use by subsequent queries. We introduce MemSeeker, an implementation of QTMC that unifies efficient agentic search and persistent memory construction through structured search trajectories. Its cited working notes support efficient reasoning during search and serve as inputs to deterministic memory construction after answering. Evaluated on 2,400 questions spanning eight heterogeneous benchmarks, MemSeeker uses 83.5% fewer tokens while retaining comparable accuracy to the strongest baseline. Further analysis identifies two ways persistent memory supports subsequent queries: supplying evidence for direct answers and guiding the search for missing information. Code is available at https://anonymous.4open.science/r/Memseeker-Query-Time-Memory-Construction-0D3B.