ArcMemo: Abstract Reasoning Composition with Lifelong LLM Memory

TL;DR

When an LLM reasons hard through a problem, it discovers useful patterns — and then throws them away the moment the context window resets for the next query. ArcMemo’s fix is concept-level memory: after a problem is solved, a model writes down the general, modular ideas it used (not the whole solution) as natural-language entries, and for a new problem it selects the handful of concepts likely to help and pastes them into context. Tested on ARC-AGI-1 (a benchmark built to resist memorization), the structured “program-synthesis” variant lifts the official score from 55.17 to 59.33 (+7.5% relative) over a strong no-memory baseline, and it’s the only memory design that beats the baseline at every level of inference compute. Crucially, updating the memory during evaluation keeps improving the score across retries — the system literally learns from its own solves at test time, no weight updates required.

Problem & Motivation

Here is the concrete pain. You run an expensive reasoning model (o4-mini, with 32k reasoning tokens) on a hard problem. It explores, backtracks, and eventually nails it. Embedded in that trace are genuinely reusable insights — “when you see X-shaped structure, try counting then sorting.” The next query comes in, the context window clears, and all of that is gone. The model re-derives the same ideas from scratch, burning tokens to rediscover what it already knew an hour ago. Humans don’t do this: we abstract a pattern once and reapply it.

External memory is the obvious fix, and prior work tried it. But the dominant approaches store memory in a form that doesn’t transfer well:

• Instance-level memory (e.g., Buffer of Thoughts) stores entries tightly coupled to the original problem — full solution templates, query/response pairs. If puzzle 1 used ideas A+B+C bundled together, that bundle only fires again for problems that look like puzzle 1. For a new problem that needs B combined with D (from a different stored puzzle), the model has to first ignore A and C, then disentangle B from its bundle. High friction, low reuse.
• Monolithic-blob memory (Dynamic Cheatsheet) keeps one ever-growing summary buffer, rewritten on every query and pasted whole into the prompt. No structure, no selective retrieval — so it can’t scale: the buffer eventually overflows the context window, and the model has to find the relevant needle in a bigger and bigger haystack itself.

The opportunity ArcMemo names: move to concept-level memory — small, abstract, modular pieces that decouple from their origin problem and recombine freely. That’s the right granularity for compositional reasoning, where the test isn’t “have I seen this exact problem” but “can I assemble known pieces in a new arrangement.”

What’s New (Core Contribution)

1. Concept-level memory entries instead of instance-level ones. Before: memory stores composed solutions or query/answer summaries glued to one problem. Now: memory stores individual, context-light “concepts” (a situation→suggestion rule, or a typed parameterized routine) that are easier to recognize and recombine across superficially different problems.
2. A program-synthesis (PS) memory format that imports functional-programming discipline. Before: free-text notes that drift toward overly-specific implementation detail. Now: concepts framed as typed, parameterized types/structures/routines — including higher-order routines (a routine can take another routine as a parameter). Type annotations on inputs/outputs literally tell the model which concepts plug into which, encoding modularity directly in the representation.
3. Reasoning-based selection (read), not embedding similarity. Before: retrieve by vector cosine similarity (one forward pass, “System 1”). Now: a reasoning model deliberately explores the concept library (“System 2”) — start from relevance cues, then chase type annotations to fill in parameters — because abstract concepts are too far from the concrete problem for embeddings to match reliably. (The paper shows embedding retrieval actually hurts: score dropped 0.26→0.22.)
4. Demonstrated test-time continual learning. Before: memory is usually frozen at eval time to avoid order effects. Now: updating memory mid-evaluation (every 10 problems) measurably improves later passes — solves found on pass 1 seed concepts that unlock new solves on pass 2. This is the lifelong-learning payoff, shown empirically.

How It Works (Technically)

ArcMemo is a thin wrapper around any reasoning LLM, defined by three design surfaces that every memory system must answer (the paper’s framing in Algorithm 1):

1. Memory Format — what is stored in one entry?
2. Memory Write — how do you turn a solved trace into entries?
3. Memory Read — how do you pick entries for a new problem?

The whole system is the loop in Algorithm 1: for each problem, read relevant concepts, generate a solution with the LLM conditioned on those concepts, and — every k problems — get feedback (here, run the candidate program against the puzzle’s example grids) and write new concepts back. Let’s walk each surface, then trace one problem end to end.

Memory Format — what an entry looks like

Two implementations, escalating in structure:

Open-Ended (OE). Minimal constraint: each entry has exactly two fields — a situation (“when you see a grid with isolated colored objects…”) and a suggestion (“…try counting them and drawing a bar per count”). The situation is the retrieval hook; separating it from the suggestion is what decouples the idea from its origin problem. The model is otherwise free to phrase entries however it likes.

Program Synthesis (PS). The workhorse. Borrowing from functional programming, each concept is a typed, parameterized object with fields (full list in the paper’s appendix): Title, Description, Kind (type / structure / routine), Parameters, Output Typing, Relevance Cues, Implementation Notes. Two ideas do the heavy lifting:

• Parameterization lets one concept cover a family of variations. “Sort objects” isn’t one entry per sort order; it’s a sort_objects(key: Callable) concept where the variation lives in a parameter. A higher-order parameter (a routine passed as an argument) abstracts over logic, not just values — this is what lets the library stay compact as it grows.
• Typed interfaces make composability legible. If concept A outputs List[Object] and concept B consumes List[Object], the type annotation tells the selecting model “B can run after A.” Modularity isn’t a hope; it’s encoded.

The PS format is also compressible: when the library is pasted in during abstraction, you can drop fields (e.g., Implementation Notes) to save tokens.

Memory Write — turning a solve into concepts

OE write is a straight reflection query: “Here’s a solved trace; summarize the general, reusable ideas as situation→suggestion pairs.” A wrinkle: commercial models often hide their reasoning trace, and intermediate inferences may be implicit. So ArcMemo reconstructs a post-hoc derivation — an interleaved observation/reasoning narrative built backward from the final input→output solution — and extracts situation/suggestion pairs from that. OE write is deliberately memory-unaware (it doesn’t look at existing entries), deferring de-duplication to the read/solve stages.

PS write is more careful. Directly converting code to “routines” tends to record low-level junk, so the solution is first rewritten into pseudocode to bias toward high-level operations. Then the abstraction step runs with a compressed view of existing memory in context, and is explicitly instructed to reuse and revise existing concepts (update descriptions, add parameters, refine relevance cues) rather than spawn near-duplicates — and to prefer higher-order routines. Every write is scaffolded with few-shot demonstrations and rich templates.

Memory Read — selecting concepts for a new problem

You can’t paste the whole library — it overflows context and floods the model with distractor hypotheses. So selection is essential.

OE selection is a preprocessing trick. ARC is spatial, so a vision-language model captions each puzzle with a structured prompt that separates concrete observations from speculative transformations. That caption converts pixel grids into natural language that can be matched against the stored situation fields. Then a model is asked for the top-k most relevant entries (they tried thresholding and top-p; top-k won on simplicity).

PS selection is the System-2 version. Because PS concepts are abstract, a single embedding pass can’t reliably connect them to a concrete puzzle. Instead a reasoning model explores the library with backtracking: first surface candidate concepts via their relevance cues, then “fill in the details” — figure out what values/routines populate each candidate’s parameters, using type annotations to decide which other concepts to investigate next. It’s a directed search over the concept graph rather than a nearest-neighbor lookup.

Architecture & data flow

flowchart LR
  subgraph WRITE[Memory Write -- after a solve]
    T[Solved trace] --> PD[Post-hoc derivation / pseudocode]
    PD --> AB[Abstraction LLM<br/>aware of existing concepts]
    AB --> M[(Concept Library<br/>typed, parameterized,<br/>modular)]
  end
  subgraph READ[Memory Read -- new problem]
    X[New puzzle grids] --> CAP[VLM caption /<br/>relevance-cue match]
    CAP --> SEL[Reasoning selector<br/>top-k + type-guided search]
    M --> SEL
    SEL --> S[Selected concept subset]
  end
  X --> GEN[Reasoning LLM<br/>generate program]
  S --> GEN
  GEN --> YH[Candidate program]
  YH --> VER{Verify vs<br/>example grids}
  VER -- pass --> OUT[Prediction]
  VER -- fail --> RETRY[Retry w/ execution feedback]
  RETRY --> GEN
  OUT -. every k problems .-> T

Schematic: why modular concepts beat bundled ones. Drag the concept tiles to compose a solution for the target puzzle. Instance-level memory forces you to accept whole bundles (and then ignore the parts you don't want); concept-level memory lets you grab exactly the pieces you need from different past problems. This illustrates the paper's Figure 1 intuition, not its data.

The algorithm, simplified

The contribution is the loop, not any single model call. Here it is with the model calls stubbed and the novel parts spelled out:

# Inference with a continually-updating concept memory (paper's Algorithm 1).
# llm(prompt) -> str ; vlm_caption(grids) -> str ; run(program, examples) -> Feedback
# memory: list of Concept objects (typed, parameterized) -- starts from seed solutions.

def solve_dataset(problems, memory, k=10):
    preds = []
    for i, p in enumerate(problems):
        # READ: don't dump the whole library -- select a relevant subset.
        desc = vlm_caption(p.grids)                  # spatial -> language, so it can match concepts
        concepts = reasoning_select(memory, desc)    # System-2 search: relevance cues -> type-guided fill-in

        # GENERATE: condition the solver on ONLY the selected concepts.
        program = llm(solve_prompt(p, concepts))     # asks for a transform function, not the raw grid
        feedback = run(program, p.examples)          # execution feedback = the verification signal

        # Retry loop uses the feedback to repair (sequential inference scaling).
        for _ in range(p.max_retries):
            if feedback.passes: break
            program = llm(repair_prompt(p, program, feedback))
            feedback = run(program, p.examples)

        preds.append(program)

        # WRITE (only every k problems, and only from CORRECT traces):
        # abstracting a flawed trace would carry mistakes forward.
        if i % k == 0 and feedback.passes:
            pseudocode = llm(to_pseudocode(program))         # bias toward high-level ops
            memory = abstract_concepts(pseudocode, memory)   # REUSE/REVISE existing entries, prefer higher-order routines
    return preds

The two lines that make this paper are reasoning_select (read by deliberate search, not cosine similarity) and abstract_concepts (write that is aware of and revises existing memory, into typed/parameterized form). Everything else is standard agentic plumbing.

One subtlety worth flagging: the write gate requires feedback. ArcMemo only abstracts from verified-correct traces, because storing patterns from a wrong trace propagates errors. That’s the load-bearing assumption — see Results caveats.

Built on Prior Work

The honest positioning: the operations (read/write memory, reflect, retry) are all known. The genuine novelty is the representation (abstract, typed, modular, higher-order concepts) and the read mechanism matched to it (reasoning-based selection). MemP is concurrent work with a similar abstraction thesis but aimed at agentic action sequences rather than general problem-solving.

Results & Evidence

Setup. ARC-AGI-1, a 100-puzzle subset of the public validation split (following Akyürek 2025, for cost/variance reasons). Solver = OpenAI o4-mini (medium, 32k tokens); auxiliary abstraction/selection = GPT-4.1. Memory seeded with 160 hand-written solutions from Li et al. Evaluation uses a program-synthesis protocol (model emits a transform function, which is run against example grids — that execution is the feedback/verification signal) and the official oracle@2 metric (two attempts, credit if either passes). Scores averaged over 3 runs due to high sampling variance. Primary baseline: a re-implementation of Dynamic Cheatsheet (“cheatsheet”).

Headline numbers (oracle@2, official):

What the evidence does establish:

• ArcMemo-PS is the only memory design that beats the no-memory baseline at every inference-compute scale (more parallel samples × more sequential retries). OE and Cheatsheet sometimes underperform the baseline.
• Memory helps most at low compute — exactly the “stop rediscovering ideas” thesis. At high compute the model can re-derive ideas by brute exploration, shrinking memory’s marginal value.
• Selection ablation: removing reasoning-based selection drops the score (59.33→55.17 at base scale) and burns far more tokens. Selection helps quality and efficiency, not just context budget.
• Attribution: for the selection-free comparison vs. Cheatsheet, both solve the same total puzzles but differ on 10. 100% of ArcMemo’s new solves trace to actual concepts in memory; only 40% of Cheatsheet’s do. Weak evidence, but suggestive that ArcMemo’s gains come from memory rather than noise.
• Continual learning: updating memory every 10 problems beats frozen memory — but only at high retry depth (later sequential passes), consistent with “new solves seed new concepts that unlock more solves.”

What it does NOT establish (read this before selling it):

• Tiny, noisy benchmark. 100 puzzles, high variance, gains in the low single digits absolute. The authors are upfront: the effect lives on a “small frontier” of puzzles where memory can flip an outcome.
• No ARC-AGI-2. The harder successor (SOTA <30%) released mid-project; untested. Whether abstraction memory helps where the baseline is far weaker is unknown.
• The correct-trace gate is doing a lot of work. ArcMemo assumes cheap, reliable verification (here: run the program against example grids). In domains without an oracle, you’d write garbage concepts into memory. Error-trace credit assignment is explicitly left to future work.
• Embeddings failed; the alternative is expensive. Reasoning-based selection works but costs autoregressive generation per query, not a vector lookup. The token-efficiency plot shows memory runs often increase output tokens (the model explores more hypotheses).
• Continual-update gain is small and order-dependent. It introduces an accuracy/throughput trade-off (batching breaks ordering); most experiments used frozen memory to avoid the confound.

How You’d Use It

For someone running agentic systems and an AI services shop, ArcMemo is a memory pattern, not a model — and a directly transplantable one.

• A “learns-on-the-job” layer for a vertical agent. Any client workflow with cheap verification (code that compiles + passes tests, SQL that returns expected rows, a config that validates, a form that reconciles) can run the loop: solve → if verified, abstract the lesson into a typed concept → next similar ticket pulls those concepts in. Over weeks the agent stops re-deriving the same domain tricks. This is a genuine differentiator vs. a stateless GPT wrapper: a deployment that visibly improves on the client’s own data without retraining.
• Replace your RAG-of-transcripts with concept memory. Most “agent memory” today is RAG over past conversations — instance-level, exactly the thing this paper shows transfers poorly. For reasoning-heavy tasks (debugging, planning, analysis) a concept library of abstracted strategies is the better store. You can keep your vector DB for facts and add a concept tier for know-how.
• Selection > stuffing. The ablation is the practical lesson: don’t paste your whole knowledge base into context. A reasoning-based “which of these strategies actually apply here” pass improves both quality and cost. That’s a cheap upgrade to almost any existing RAG pipeline.
• The typed-interface idea is a moat-builder. A hand-curated, typed concept library for a niche (e.g., “lease-abstraction tactics,” “ETL repair patterns”) is defensible IP that compounds. The composition-by-type trick keeps it usable as it grows.

Realistic effort: a usable prototype is days, not months (it’s prompt engineering + a store + a verifier). The hard part is the verifier and the abstraction quality — see below.

Build Your Own (Minimal Recipe)

Smallest version that captures ~80% of the value:

1. A concept store. Start dead simple: a flat JSON/SQLite list of concept dicts {title, when_to_use, how_to_use, params, depends_on_types, returns_type}. No vector DB needed — the paper’s selection is LLM-driven, not embedding-driven.
2. A verifier for your domain. This is non-negotiable and the real work. You need a cheap boolean “did this solve work?” (tests pass, output matches spec, schema validates). Without it, do not auto-write to memory.
3. The write step. After a verified solve, one LLM call: “Here’s the task and the working solution. Extract the general, reusable strategies as concept entries. Here is the current library (compressed) — reuse/revise existing concepts instead of duplicating; prefer parameterized, composable ones.” Pseudocode-first if your solutions are code.
4. The read step. Two LLM calls: (a) describe the new task in the vocabulary of your when_to_use cues; (b) ask a reasoning model to pick the top-k relevant concepts and reason about how they’d combine. Inject only those.
5. The loop + retry. Generate → verify → retry with feedback (0–2 retries buys a lot here) → on success, periodically write.

Libraries/models: any reasoning model for solve+select (o4-mini-class or better), a cheaper model (GPT-4.1-class) for abstraction to save tokens, plain Python for the store and loop. Skip embeddings on v1 — the paper found them worse.

The two genuinely hard parts: (1) the verifier — everything depends on only writing correct concepts; (2) abstraction quality — getting the model to write general concepts rather than overfit implementation notes (their fix: pseudocode-first + library-aware, reuse-don’t-duplicate prompting).

How to Improve It

1. Learn from failures, not just successes. The current gate discards every wrong trace, throwing away signal. Add credit-assignment: identify the one wrong step, abstract the anti-pattern (“when X, do NOT do Y”). This is the paper’s own biggest acknowledged gap and the highest-leverage extension.
2. Hierarchical consolidation. Right now writes are purely additive — the library grows monotonically and can accumulate near-duplicates. Add a periodic “consolidate” pass that merges, generalizes, and prunes concepts (cluster → rewrite into a parent concept). The authors flag this as the key future direction; it’s where the “lifelong” claim gets real teeth.
3. Cheaper selection via a hybrid. Reasoning-based selection is accurate but costs full generation per query. Try embeddings as a coarse pre-filter (top-50) feeding the reasoning selector (top-k), recovering vector-lookup speed without the lexical-overfitting failure mode they observed.
4. Confidence-weighted concepts. Track each concept’s hit/miss rate when it was selected; down-rank concepts that get pulled in but never help. Turns the flat library into a self-pruning one and directly attacks the “distractor concepts” noise.
5. Order-robust continual updates. The accuracy/throughput trade-off from evaluation order is real. A small experience-replay buffer (revisit earlier problems after memory grows) or a curriculum (easy→hard so concepts compound) could capture the continual-learning gain without the batching headache.
6. Test where the baseline is weak. All gains here are on puzzles the baseline nearly solves. Run it on ARC-AGI-2 or genuinely unsolved puzzles to see whether abstraction creates new capability rather than just stabilizing marginal solves.

Glossary

• ARC-AGI — François Chollet’s benchmark of pixel-grid puzzles; each puzzle gives a few input→output grid examples and you must infer the transformation rule. Designed to reward acquiring new skills, not memorizing them.
• Compositional generalization — solving a new problem by recombining known pieces in an arrangement never seen during training/experience. ARC’s core challenge.
• Concept-level memory — storing small, abstract, reusable ideas decoupled from any one problem, vs. instance-level memory (whole solutions tied to their origin problem).
• Instance-level memory — memory entries glued to the specific problem they came from (query/answer pairs, full solution templates); low transfer to new problems.
• Higher-order function — a function that takes another function as an argument (or returns one). Here, a concept whose parameter is itself a routine, letting one concept abstract over many variations of logic.
• Typed interface — declaring a concept’s input and output types so the system can see which concepts can be chained (output type of A matches input type of B).
• Test-time / inference-time learning — improving behavior after deployment by changing the prompt/context (here, the memory) rather than the model weights. Parameter-free.
• Continual / lifelong learning — a system that keeps improving from new experience over its lifetime without manual retraining.
• RAG (Retrieval-Augmented Generation) — fetch relevant external text by embedding similarity and add it to the prompt; designed for factual knowledge, not reasoning strategies.
• Dynamic Cheatsheet — baseline memory method that keeps one growing summary blob, rewritten each query and pasted whole into context (no selective retrieval).
• System 1 vs. System 2 — fast intuitive response (one forward pass / embedding lookup) vs. slow deliberate reasoning (multi-step search with backtracking). ArcMemo’s selection uses System 2.
• Program synthesis — having the model emit a program (transform function) as its answer; the program can be executed to verify correctness, giving a clean feedback signal.
• oracle@k — scoring metric: a test case counts as solved if any of the k sampled attempts passes it. ARC’s official setting is k=2.
• Post-hoc derivation — a reconstructed observation→reasoning narrative built backward from a final solution, used when the model’s real reasoning trace is hidden, so concepts can still be extracted.
• Top-k / top-p selection — keep the k highest-scoring items, or the smallest set whose cumulative score passes a threshold p. ArcMemo uses top-k for simplicity.
• Seed memory — initial concepts the library starts with (here, abstracted from 160 hand-written ARC solutions) before any self-generated learning.