CoALA

Full title: Cognitive Architectures for Language Agents Authors: Theodore R. Sumers*, Shunyu Yao*, Karthik Narasimhan, Thomas L. Griffiths (Princeton University; *equal contribution, order by coin flip) Venue/year: Transactions on Machine Learning Research (TMLR), 02/2024 — arXiv:2309.02427 (v3: Mar 2024) Links: arXiv · local PDF: research-papers/2309.02427-coala.pdf

Why this paper matters

CoALA is the field's shared vocabulary. In 2023 every agent paper invented its own terms — "tool use," "grounding," "skills," "reflections" — making systems impossible to compare or compose. CoALA reaches back to symbolic AI's cognitive architectures (Soar above all) and shows that LLM agents recapitulate that older program: an LLM is a probabilistic production system (§3.1), prompt engineering is its control flow (§3.2), and a full agent needs exactly what Soar needed — working + long-term memory modules, a structured action space split into internal and external actions, and a decision-making loop that chooses among them (§4). It contributes no benchmark; it contributes the coordinate system. When we say an agent "writes to episodic memory" or "has retrieval and learning actions," we are speaking CoALA — and the paper's Table 2 shows the payoff, casting SayCan, ReAct, Voyager, Generative Agents, and Tree of Thoughts into one grid where their differences become three checkbox columns.

The problem

Language agents worked but had no theory. Early agents used LLMs to directly emit actions; later ones added reasoning, planning, and long-term memory — but "individual works use custom terminology to describe these processes... making it difficult to compare different agents, understand how they are evolving over time, or build new agents with clean and consistent abstractions" (§1). Meanwhile, the classic cognitive-architecture literature — production systems with preconditions and actions, Soar's decision cycle, its procedural/semantic/episodic memory split (§2.3) — had already solved the organizational problem decades earlier, but fell out of favor because symbolic systems were "limited to domains that can be described by logical predicates and require many pre-specified rules" (§2.3). LLMs remove exactly those two blockers: they operate over arbitrary text and learn a distribution over productions from pretraining. What was missing was the bridge — a framework importing cognitive-architecture structure into LLM agent design.

The mechanism

LLMs as probabilistic production systems (§3)

A production system rewrites strings by rules (X Y Z → X W Z). An LLM defines a distribution over rewrites: given prompt X, it samples a completion, X ⇝ X Y (§3.1). Prompting methods are then sequences of productions — zero-shot, few-shot, RAG, Socratic models, self-critique each pre-process the input string before the sampled production fires (Table 1, §3.2). Chains of LLM calls are algorithms; agents close the loop with an environment (§3.3). This analogy is what licenses the import: the controls developed for production systems (cognitive architectures) should apply to LLMs.

Memory modules (§4.1)

LLMs are stateless; agents are not. CoALA organizes agent state into:

• Working memory — active, readily available information for the current decision cycle: perceptual input, active goals, intermediate reasoning results. Crucially it is "a data structure that persists across LLM calls" — each LLM call is synthesized from a subset of working memory via a prompt template, and outputs are parsed back into it. It is the hub connecting LLM, long-term memories, and grounding.
• Episodic memory — experience from earlier decision cycles: trajectories, event histories, input-output pairs. Retrieved to support reasoning; written to as a form of learning.
• Semantic memory — knowledge about the world and the agent itself. Classic RAG "can be viewed as retrieving from a semantic memory" that is fixed and read-only; agents may also write LLM-derived inferences into it (as Reflexion and Generative Agents do).
• Procedural memory — two forms: implicit (the LLM's weights) and explicit (the agent's code — both the procedures implementing actions and the procedure implementing decision-making itself). Unlike the other stores it must be initialized by the designer, and writing to it is "significantly riskier... as it can easily introduce bugs or allow an agent to subvert its designers' intentions."

The action taxonomy (§4.2–4.5, Figure 5)

• External / grounding actions (§4.2): interact with physical environments, humans/agents via dialogue, or digital environments (games, APIs, code). Stateless APIs packaged as "tools" are "single-use digital environments."
• Internal actions, split by which memory is touched and whether it is read or written:
  • Retrieval (§4.3) — read long-term memory into working memory (rule-based, sparse, or dense; e.g. Voyager's skill retrieval, Generative Agents' recency/importance/relevance scoring).
  • Reasoning (§4.4) — read and write working memory via the LLM: summarize, distill, plan. Supports both decision-making and learning.
  • Learning (§4.5) — write to long-term memory: store episodes, write reflections into semantic memory, fine-tune the LLM, or update agent code (prompt templates, code skills; updating retrieval/learning/decision-making procedures is flagged as unstudied and risky). Modifying and deleting memory ("unlearning") is called out as understudied.

Figure 5's one-liner: reasoning and retrieval are the planning substrate; learning and grounding are the result actions a cycle commits to.

Decision-making (§4.6)

The top-level "main" program is a loop of decision cycles. Each cycle runs a planning stage — reasoning and retrieval actions used freely to propose candidate actions, optionally evaluate them with values (heuristics, LLM perplexity, learned values, or LLM-simulated rollouts), and select one (argmax, softmax, majority vote) — then an execution stage that runs the chosen grounding or learning action's procedure. An observation may come back; the cycle repeats. Most 2023 agents collapse this to propose-only with a single action; ToT and RAP implement genuine propose-evaluate-select via tree search/MCTS (§4.6).

The algorithm

CoALA is a framework, so its "algorithm" is the decision cycle itself — reconstructed from §4.6 and Figure 4B:

# Designer-initialized state
procedural_mem = { LLM_weights, agent_code }     # code = action procedures + this loop
episodic_mem   = []        # past trajectories/events
semantic_mem   = KB        # world/self knowledge (may start empty)
working_mem    = {}        # goals, recent observations, intermediate results

loop forever:                                   # the "main" procedure
    obs = perceive()                            # dialogue / physical / digital
    working_mem.update(obs)

    # ---- PLANNING STAGE (internal actions only) ----
    candidates = propose(working_mem)           # reasoning (+ optional retrieval):
                                                #   episodic  -> relevant past episodes
                                                #   semantic  -> relevant facts
                                                #   procedural-> relevant skills/prompts
    if len(candidates) > 1:
        values = evaluate(candidates)           # heuristics | LLM value | perplexity |
                                                # LLM-simulated rollouts
        action = select(candidates, values)     # argmax | softmax | majority vote
    else:
        action = candidates[0]                  # most 2023 agents stop here

    # ---- EXECUTION STAGE (one result action) ----
    if action.is_grounding():                   # EXTERNAL
        feedback = environment.execute(action)  # API call, motor command, utterance
        working_mem.update(feedback)
    else:                                       # INTERNAL: learning
        commit(action)                          # write episode to episodic_mem,
                                                # write knowledge to semantic_mem,
                                                # fine-tune LLM, or edit agent code

Walkthrough:

• Designer bootstrap — procedural memory is the only store that cannot start empty (§4.1): someone must write the loop, the prompt templates, and the parsers. Everything else can be learned.
• perceive → working_mem — grounding procedures render the world as text; the agent's life is "a text game with textual observations and actions" (§4.2).
• propose — reasoning generates candidates; retrieval feeds it. This is where ReAct's "thought" lives, and where Generative Agents pull scored memories before planning (§4.3–4.4). Proposal may emit one action (SayCan enumerates its fixed 551 skills instead, §5) or many.
• evaluate / select — optional sub-stages most agents skip. ToT is the existence proof that they matter: it is only proposal-evaluation-selection over reasoning actions, with tree search providing backtrack and lookahead (§5).
• The execution fork is the taxonomy — a cycle terminates in exactly one result action: change the world (grounding) or change yourself (learning). CoALA's sharpest reframe is that learning is not a separate training phase but "a result action of a decision-making cycle just like grounding" — an agent may deliberately choose when to learn, and could even "defer" it (§7, "Learning vs. acting").
• Loop — feedback enters working memory and the next cycle begins; there is no return value because the agent is a procedure, not a function (§4).

Results that matter

A framework paper — there are no benchmarks; the "result" is the classification power. Table 2 (§5), verbatim structure:

("—" = no writable long-term memory; all agents have procedural memory in the trivial sense of code + weights, footnote to Table 2.) Read across the rows: capability grows left to right and down the table, and the grid exposes what each system lacks — ReAct has no memory to learn into; ToT has memory-free deliberation; nothing in the table does propose-evaluate-select and full memory. That empty cell is the paper's implicit research agenda (§6).

Limitations & how to defend the findings

• "It's just a survey with diagrams — nothing is falsifiable." Partly conceded: the paper positions itself as combining a theoretical framework and empirical organization (§1), and its value claim is pragmatic — shared abstractions reduce technical debt and enable comparison, argued by analogy to MDPs/OpenAI Gym for RL (§6, "Modular agents"). The defense is Table 2: if the framework cleanly expresses five very different agents without residue, the abstraction is doing work.
• "The Soar analogy is decorative — LLMs aren't production systems." §3.1 makes the correspondence precise (an LLM defines P(Y|X) over productions) but also names the disanalogy honestly: LLMs are opaque and stochastic where productions are discrete and legible. The paper's response is to use code sparingly — deterministic structure only where LLM limitations demand it, e.g. tree search to counter autoregressive myopia (§6, "LLMs vs. code").
• "Boundaries are arbitrary — is Wikipedia memory or environment?" The paper raises this against itself (§7) and offers a test: controllability (only-agent-writable ⇒ internal memory) and coupling (co-designed prompts ⇒ one agent, not two). Practitioners "may also just choose their preferred framing, as long as it is consistent."
• "It's frozen in 2023 — better models dissolve the architecture." Addressed head-on in §7 ("GPT-4 vs GPT-N"): agent design is a moving target, and a strong enough LLM could "simulate" memory and decision-making internally. The framework's bet is that even then, memory/actions/decision-making remain the right design dimensions — a claim the reader must judge; the paper offers argument, not evidence.
• "No guidance on hard trade-offs." Fair at the quantitative level. Qualitatively §6 does commit: minimal action spaces are preferable (size vs. decision-complexity trade-off), learning actions are the risky part of the action space, and retrieval-learning ("updating retrieval") is an unstudied gap.

Connections

• MemGPT is a CoALA instance: working context = working memory, recall storage = episodic, archival storage = semantic, function schema + system prompt = explicit procedural memory; its self-editing calls are CoALA's internal learning actions, its heartbeat loop a propose-only decision cycle.
• Generative Agents occupies CoALA's richest row (Table 2): all four action types, episodic and semantic memory — reflection is exactly "reasoning used for learning" (§4.4–4.5), retrieval is the recency/importance/relevance score (§4.3).
• Voyager is the procedural-learning existence proof: its skill library is writable procedural memory, the one store CoALA calls risky to touch — and the case study (§5) notes ablating that library breaks it.
• The episodic/semantic/procedural taxonomy now structures the memory literature wholesale: Letta's blocks, Mem0, Zep's temporal graph, and AriGraph's semantic-triplet + episodic-vertex split all report themselves in CoALA vocabulary.
• Tree of Thoughts / RAP as decision-procedure upgrades: CoALA frames deliberate planning (propose-evaluate-select, MCTS) as orthogonal to memory — the two axes our survey briefs track separately (orchestration vs. memory) are Table 2's columns.
• Soar (Figure 2) is the design ancestor worth actually reading about: its chunking, impasse-driven subgoaling, and RL-tuned productions prefigure skill learning, escalation, and preference optimization in modern agents.

Reading guide

• Read first: §4 in order (4.1 memory → 4.2–4.5 actions → 4.6 decision-making) — the framework proper, ~5 pages. Then §5 case studies to see it applied.
• The one figure to study: Figure 4 — panel A is the module diagram (procedural/semantic/episodic memory around working memory and the decision procedure), panel B is the decision cycle (Proposal → Evaluation → Selection → Execution). Table 2 is the payoff and the best exam-style self-test: cast a new agent into it from memory.
• Read for depth: §2.3 (Soar — memory, decision loop, learning modes; the template for everything in §4) and §3.1–3.2 (the production-system analogy that justifies the import; Table 1 is a compact gem).
• Skimmable: §2.1–2.2 (string-rewriting history), §6's industry bullets, and the long citation lists in §4.2.
• Do not skip in §7: "Internal vs. external" (the controllability/coupling test) and "Learning vs. acting" — the two discussions with the most design leverage per paragraph.