LLMs Can't Play Hangman: On the Necessity of a Private Working Memory for Language Agents

arXiv:2601.06973v2 Announce Type: replace Abstract: As LLMs move from text completion toward autonomous agents, they remain constrained by the standard chat interface, which lacks private working memory. This raises a fundamental question: can agents reliably perform interactive tasks that depend on hidden state? We define Private State Interactive Tasks (PSITs), which require agents to generate and maintain hidden information while producing public responses consistent with a fixed hidden state. We show theoretically that any agent restricted to the public conversation history cannot both keep the secret unresolved in the transcript and respond consistently with a fixed hidden state in PSITs, yielding an architectural impossibility theorem. To empirically validate this limitation, we introduce a self-consistency testing protocol that evaluates whether agents can maintain a hidden secret across forked dialogue branches. Standard chat-based LLMs and retrieval-based memory baselines fail this test regardless of scale, demonstrating that semantic retrieval does not enable true state maintenance. To address this, we propose a novel architecture incorporating an explicit private working memory; we demonstrate that this mechanism restores consistency with a fixed hidden state, establishing private state as a necessary component for PSIT-capable language agents. Our code is available at https://github.com/chandar-lab/Hangman

Related

• Memp: Exploring Agent Procedural Memory
• MemoryForge: Synthesize Lifelong Memory for Human-Like LLM Agents
• A Survey on the Security of Long-Term Memory in LLM Agents: Toward Mnemonic Sovereignty
• Memory in the LLM Era: Modular Architectures and Strategies in a Unified Framework
• CLAG: Adaptive Memory Organization via Agent-Driven Clustering for Small Language Model Agents

Source: arXiv cs.CL | 2026-09-01