LLMs Are Not Good Strategists, Yet Memory-Enhanced Agency Boosts Reasoning

AI summary

Overview

• Research area: LLM-based agents, long-horizon strategic reasoning, memory-augmented decision-making, with StarCraft II as the evaluation testbed.
• Technical level: Intermediate. The retrieval, gating, and memory-fusion mechanics are described in detail, but the underlying ideas (case-based reasoning, working vs. episodic memory) are accessible without a deep RL background.
• Scope: The paper introduces EpicStar, a framework that stores past winning gameplay episodes in memory and reuses them as a policy-like heuristic, showing higher win rates at lower token cost than a strong summarization-based baseline in StarCraft II.

What This Paper Is About

Large language models are competent at short reasoning tasks but degrade over long horizons, where finite attention prevents them from holding a strategy together across thousands of steps. The authors call this failure "strategic drift": the agent overfits to local observations and slowly loses sight of its global objective. The goal is to replace reactive prompting with structured reuse of past experience, so an agent can stay strategically coherent in dynamic, partially observable environments without spending enormous amounts of inference compute.

Key Contributions

1. EpicStar framework. An LLM agent architecture that maintains a bank of successful past episodes (episodic memory) alongside a short-term working memory, treating retrieved experience as an implicit non-parametric policy rather than as passive storage.
2. Situational modulation mechanism. A dynamic gating module decides at each step whether to directly execute a retrieved action or run fresh LLM reasoning, plus a contextual fusion step that lets working memory constrain retrieved episodes and lets retrieved episodes provide high-level strategic framing for exploration.
3. Empirical validation across models and difficulty levels. Evaluation against the CoS (Chain of Summarization) baseline using four OpenAI backbones (gpt-3.5-turbo, gpt-4-turbo, gpt-4o-mini, gpt-4o) at difficulty levels 5 and 6, showing consistent win-rate gains and large token savings.
4. Ablation evidence that both memory systems matter. Removing either exploration via working memory or contextual fusion degrades performance, with the effect intensifying at higher difficulty — even a small curated memory bank (4,592 episodes drawn from 5 winning games) yields marked gains.

Main Findings

• Higher win rates at both difficulty levels. At Level 5, EpicStar with gpt-4-turbo reaches 75.0% versus 60.0% for CoS with the same model; gpt-4o-mini reaches 67.5% and gpt-4o 65.0%. At Level 6, EpicStar with gpt-4o-mini reaches 30.0%, while CoS with gpt-3.5-turbo manages only 8.3%; EpicStar roughly doubles that to 15.0% with the same weaker model.
• Substantially lower inference cost. Token consumption is reported at 14.5% of the CoS baseline with matched models, described in the abstract as an order of magnitude fewer tokens. The efficiency gain comes from reusing retrieved actions instead of re-reasoning from scratch each step.
• Better macro-management metrics. Average Population Utilization (APU) rises to 0.8449 (gpt-4-turbo) and 0.7991 (gpt-3.5-turbo) versus 0.7194 and 0.7608 for CoS, indicating more effective use of the population cap. Population Block Ratio and Resource Utilization Ratio show occasional inversions, which the authors attribute to EpicStar not accepting opponent surrender, thereby prolonging games past the win condition.
• Both components are load-bearing, especially at higher difficulty. At Level 5, ablating exploration drops the win rate from 67.5% to 60.0% and ablating contextual fusion to 65.0%. At Level 6, the drops are steeper: 17.5% without exploration and 12.5% without fusion, versus 30.0% for the full agent.
• Difficulty amplifies the memory advantage. At Level 5, ablated variants perform comparably across opponent styles. At Level 6, the gap widens sharply on Power, Rush, and Timing strategies, where ablated agents fall near zero while EpicStar retains 37.5% on Power and 12.5% on Rush and Timing. The authors caution that absolute Level 6 win rates remain low, so results indicate relative robustness, not mastery.
• Faster expansion and faster victories. In a case study against a Level 6 "air" opponent, EpicStar claims additional bases earlier (at 1, 5, 8, and 11 minute marks) and closes out the game sooner than the same agent without working-memory exploration.

Methodology in Plain English

The task is framed as sequential decision-making under partial observability: the agent sees observations, not true states, and receives only a win/loss signal rather than a shaped reward.

Episodic memory. The agent stores winning games as triples of (time, observation, action), where each observation is a Python dictionary mapping units to scalar values. To retrieve relevant experience, it first narrows the bank to episodes near the current game time using binary search, then scores each candidate moment by how similar its observation is to the current one. Similarity uses two counts: how many unit types differ, and how many values differ. These are min-max normalized, averaged with equal weight (0.5/0.5), and the top three episodes are returned. If nothing matches, the retrieval returns an empty action.

Working memory. A queue holds the four most recent observations sampled at a fixed interval of 24 frames, giving the agent a short-term picture of how the game is trending without flooding the prompt.

Gating between reuse and reasoning. At each step, the agent first retrieves episodes and extracts the leading action. Separately, on a cooldown schedule, it prompts the LLM to propose a batch of exploratory actions that are pushed onto an action queue. If the retrieved action turns out to be empty and the queue is non-empty and a second cooldown has elapsed, the agent pops an exploratory action instead. This is the exploration/exploitation balance: retrieved memory handles routine play; LLM exploration covers situations memory does not cover.

Contextual fusion. Two directions of modulation connect the memory systems. Working memory constrains episodic memory by instructing the model to ensure retrieved actions are actually executable in the current scenario. Episodic memory informs working memory by having the LLM generate a high-level description of the strategy behind the retrieved episode and prepending that description to the prompt.

Setup. Episodic memory is bootstrapped by a rule-based agent playing 20 rounds against built-in opponents at Levels 6 and 7, keeping five winning games and 4,592 episodes. Evaluation happens on maps disjoint from the collection maps (Abyssal Reef LE and Ever Dream LE), with the LLM playing Protoss against built-in Zerg, 40 rounds per level per configuration (20 for the expensive gpt-4-turbo). The game interface and prompts are adapted from TextStarCraft II, with hardcoded attack and defend routines removed for flexibility. The baseline is CoS, which uses a sliding-window summary as working memory but does not learn from its own gameplay in a structured way.

Why This Matters

The paper's central claim is conceptual, not just empirical: episodic memory can function as an implicit, non-parametric policy that complements the LLM's own reasoning. A handful of well-chosen past trajectories carries more decision-relevant signal than exhaustive search or additional prompting loops. This connects LLM agent design to case-based reasoning in cognitive science and suggests that agents should learn from their own experience rather than relying only on retrieved external knowledge. It also shows that strategic coherence can be bought cheaply — an order of magnitude fewer tokens — which changes the cost calculus for deploying agents in long-running environments.

Real-world applications:

• Game AI and simulation opponents that adapt to player styles while retaining strategic identity over long matches.
• Enterprise workflow agents in support, operations, or IT triage, where resolved past cases can be replayed instead of re-derived, reducing latency and cost per action.
• Autonomous decision systems under partial observability, such as logistics routing or resource allocation, where local optimization causes drift from longer-term objectives.
• Training and tutoring systems that reuse successful interaction episodes to keep long sessions on a coherent pedagogical trajectory.

Industry relevance centers on cost and reliability: the token efficiency result means long-horizon agent deployments become economically viable, and the memory-as-policy idea offers a path to agents that improve from their own successful runs rather than from ever-larger prompts or hand-written rules.

Future Directions

• Memory scaling and noise. The authors have not characterized how performance scales with a much larger memory bank, nor how the agent behaves when stored episodes are redundant, noisy, or contradictory.
• Prompt overhead and representation. As the memory bank grows, appending episodes in natural language becomes impractical; specialized memory tokens or parameterized memory (integrating experience into model weights) are proposed as alternatives.
• Detecting inapplicable memories. A safety concern is overfitting to opponent styles encountered during memory collection. Principled ways to detect when a retrieved episode no longer applies, beyond the current gating heuristic, would make such agents safer against genuinely novel adversaries.
• Generalization beyond StarCraft II. Testing whether strategic drift and its mitigation via structured memory are general phenomena requires transferring the approach to other long-horizon, partially observable domains, and clarifying how much the performance ceiling depends on the base model's capability.

Target Audience

Researchers and practitioners working on LLM agents, planning, and long-horizon reasoning will get the most value, particularly those interested in memory architectures, retrieval-augmented decision-making, or game AI benchmarks. It is also relevant to engineers building production agents where inference cost and sustained strategic coherence are both constraints, and to cognitive-science-oriented AI researchers interested in episodic memory as a computational mechanism. The paper was presented at the ICLR 2025 Workshop on Reasoning and Planning for LLMs; readers without a reinforcement learning background can follow the memory design and evaluation, but familiarity with agent loops and retrieval systems will help.

Authors’ abstract

Strategic reasoning in Large Language Models (LLMs) within long-horizon environments is often limited by inconsistent subgoals. In these settings, finite attention resources prevent the model from maintaining strategic coherence over thousands of steps. This limitation leads to strategic drift, where localized decisions fail to sustain a coherent trajectory across reasoning. To address this, we introduce EpicStar, a framework that enables agents to learn memory as policy to tackle long-horizon reasoning. Specifically, the agent maintains a bank of successful past episodes as a heuristic alongside a working memory to track short-term environmental changes. During inference, a dynamic gating mechanism determines whether to execute a retrieved action directly or to perform new reasoning through a contextual fusion of the retrieved episodes and current working memory. Utilizing StarCraft II as the testbed, we evaluated EpicStar against diverse opponent styles. It significantly outperforms baseline methods, achieving higher win rates while consuming an order of magnitude fewer tokens, and it maintains this advantage consistently across difficulty levels and opponent strategies. Our findings provide compelling evidence that structured cross-episode memory is essential for enabling LLM agents to perform robust, long-term strategic execution in dynamic, autonomous settings.