Stop Taking Notes, Write Rules as Programs: Schema Tackles AI Memory Degradation in Unknown Environments

Forum topic · 小凯 · 2026-10-13

Summary

A new paper from CMU, UC Berkeley, and Impossible Research introduces Schema, a framework that replaces text-based note-taking with executable programs to combat memory degradation in AI agents exploring unknown environments. The key insight is that programs, unlike notes, are falsifiable: they can be replayed against historical interactions to verify whether their predictions match reality. Schema has four components—hypothesis (encoding understanding as programs), certification (history replay verification), planning, and verified execution. Ablation studies on ten hardest games show verified execution matters most: removing it drops performance from 72.9% to 52.4%, more than switching to text notes (58.8%). On ARC-AGI-3 (25 games, 183 levels), Schema raised best-model human-action efficiency from 58.7% to 99.2%, with two configurations clearing all 25 games. On DiG-bench, it cut per-level cost by ~15% to $3.40 while winning more. On MazeBench (256 rooms, 100 gems), it reached the median of the top 50 human players who averaged 37.2 hours. The authors note limits: validation is only demonstrated in games/simulations where resetting is free, and the 'human-level' claim deserves caution.

Stop Taking Notes, Write Rules as Programs

What happens when you let an AI play a game it has never seen? It mashes buttons randomly, stumbles a few times, and starts taking notes: "stepping on the red block makes you bounce," "pull the lever first, then the door opens." Sounds smart. The problem: as the game gets deeper and interaction logs pile up, notes get compressed and rewritten repeatedly—hours later, the AI has forgotten its earliest lessons and falls into the same pit again. Researchers call this memory degradation; anyone who has worked on long-horizon exploration benchmarks like ARC-AGI-3 knows the scene well.

A team from CMU, UC Berkeley, and a group called Impossible Research proposes a new cure for this old ailment in a recent paper: don't record with text, record with programs.

Notes vs. Programs

The difference isn't format—it's whether the record can be run.

A note merely states: "after pulling the lever, the door opens." A program is a promise: given your current position and action, I can compute what the world will look like next. Notes are past tense; programs are future tense. Notes can't be falsified, programs can—replay them against history, check predictions against what actually happened, and mismatches mean the program is wrong.

The paper calls this approach interactive program induction. The AI explores while writing "how I think this world works" as an executable program; each newly learned mechanism adds a rule; every rule must pass a historical consistency check—replaying past interactions to see whether the program's predictions match actual outcomes. Mismatches mark what to investigate next.

This is isomorphic to how scientists work: observe, hypothesize, test with experiments, revise. The only difference: the hypothesis must be written in a machine-executable form.

Four Components: Which Matters Most

The framework, called Schema, has four parts: hypothesis (encoding understanding as programs), certification (verifying programs via history replay), planning (searching for action plans within the program), and verified execution (checking program predictions against real-world feedback at every step).

Which component matters most? Ablation studies rank them—on the ten hardest games, dismantling the full framework (72.9%) piece by piece: switching to text notes drops it to 58.8%; removing certification, 62.3%; removing planning, 59.2%; removing verified execution, 52.4%.

Two counterintuitive conclusions. First, replacing text with programs does help (a 14-point gap), but it isn't the biggest contributor—the biggest is verification. Removing the pre-execution check costs 20 points, more than switching to text. Second, in other words: merely getting an AI to "write notes as code" is far from enough; you must force it to check against the real world at every step. Programs are reliable not because they're code, but because they can be caught erring at any moment.

The Results, and What's Behind Them

Results come in three parts, all external benchmarks—not home-made exams.

ARC-AGI-3, the official ARC Prize visual puzzle benchmark: 25 public games, 183 levels, completely unknown rules. With the same base model, human-action efficiency (RHAE) was 58.7% under a plain code framework and 99.2% with Schema. That best figure comes from the Fable 5 configuration; across four model configurations, scores rose overall from 1.2%–20.2% (base framework) to 86.1%–99.2%, and games fully cleared rose from at most 6 to 22–25. The two best configurations (Fable 5 and Sol) cleared all 25 games, versus 14 and 15 under their original code frameworks. The video claim of "clearing all 25 games" accurately refers to these two configurations.

DiG-bench, a hidden-rules exploration benchmark with 21 public games: GPT-6 Astra under Schema cleared every game, with fewer failed attempts and less health lost—estimated cost per level cleared was $3.40, about 15% below the base framework's $4.00. Saving money isn't surprising; saving money while winning more is.

MazeBench is the harshest test: a 3D maze with 256 connected rooms and 100 gems, testing knowledge accumulation over very long interactions. The top 50 human players on the leaderboard averaged 37.2 hours and 65,876 steps, with a median gem collection of 29%. Schema, over tens of thousands of interactions, continuously accumulated and reused knowledge, reaching roughly the median of this human group.

The Limits

First, a boundary the paper itself acknowledges: the approach has only been demonstrated in games and simulated environments. Game environments have a unique advantage—verification is free. If a program's prediction is wrong, just reset; zero cost. In the physical world, one verification might mean a broken machine. Whether the program-induction paradigm transfers to real environments remains unproven. On the project page, the team names their next destination: environments far richer than 64×64 pixel grids—"that's where we're going."

A subtler point: a human's 37.2 hours is continuous embodied learning, while the agent's tens of thousands of steps are stacked API calls—not quite the same thing. Reaching the human median is a real achievement, but read the phrase "human-level" with a grain of salt.

Even so, the paper leaves more than numbers. It redefines "AI memory": memory should not be a pile of text about what happened in the past, but a model of how the world works that can be overturned at any time. Having stored memories and completed tasks doesn't equal having learned—a judgment echoed in recent weeks by papers from different teams. Schema offers a cheap and sturdy answer: write your understanding as a program, and let it face reality's audit daily.

Paper: arxiv.org/abs/2609.39140 (Schema: Discovering Unknown Environments via Agentic Program Induction). Project page: schema-harness.github.io. Two discrepancies from the video, noted faithfully: the video says "Python programs," but the paper only says executable programs without locking a language; the video says "36 hours, nearly 30,000 steps," but the paper gives no such figure, only "tens of thousands of interactions."