PaperlayerView exact revision on arXiv

Source-linked AI summary

Schema: Discovering Unknown Environments via Agentic Program Induction

Guanning Zeng, Jiani Wang, Wenjie Ma, Shaofeng Yin, Chenyang Wang, Shichen Liu, Angjoo Kanazawa, Wode Ni, Xiuyu Li, Andrea Zanette, Haiwen Feng

arXiv:2609.39140v1cs.AI

TL;DR

LLM agents still struggle to learn unfamiliar environments with unknown rules, and prose-based records can degrade as context is compacted. Schema organizes learning and action through interactive program induction, representing discoveries as executable programs that can be checked, planned within, and tested during interaction. Across three benchmarks, Schema improves task performance, including 99.2% RHAE versus 58.7% for the same base model in its coding harness on ARC-AGI-3.

  • Problem

    LLM agents remain challenged by unfamiliar environments with unknown rules, while prose-based discoveries can degrade as context is compacted and memory is rewritten.

    Source: §1 · p. 1

  • Method

    Schema has an LLM agent express its evolving understanding as executable programs that it checks against interaction history and uses to guide experimentation and planning.

    Source: §1 · p. 2, §3 · p. 3

  • Results

    Across ARC-AGI-3, DiG-bench, and MazeBench, Schema improves performance, reaching 99.2% RHAE versus 58.7% for the same base model in its coding harness on ARC-AGI-3.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Behavioral analyses show learned rules persisting across context compactions and being reused in new situations, supporting sustained exploration over long interaction horizons.

    Source: §6 · p. 9

    The task objective prioritizes completion with few environment interactions, reflecting settings where experimentation has a cost.

    Source: §2 · p. 3

Abstract

from arXiv · show

Learning to complete tasks in unfamiliar environments with unknown rules remains a key challenge for LLM agents. Current LLM agents often record their discoveries in prose, which may not provide a compact, explicit account of how the environment works. Inspired by how scientists organize observations into testable, predictive theories, we introduce Schema, an agent harness that organizes learning and action through interactive program induction. The LLM agent decides what to investigate and how to act, expressing its evolving understanding of the environment as executable programs. The harness consists of a persistent program workspace and a small set of interfaces for checking these programs against the interaction history, planning within them, and executing plans under step-by-step verification. Schema raises ARC-AGI-3 RHAE from 58.7% to 99.2% with the same base model, solves 100% of the public DiG-bench games, and reaches the median performance of the top-50 human players on MazeBench. Extensive analysis shows the effectiveness of Schema in unknown mechanism discovery, and ablations confirm the contribution of each component.

1 Introduction

Learning in unfamiliar environments with unknown rules remains difficult for LLM agents, whose prose-based records can degrade as context is compacted. Schema instead uses executable programs to represent and refine discoveries, guiding investigation, planning, and action.

1 Introduction

  • LLM agents can handle familiar settings but still struggle to learn entirely novel environments, where even the strongest models fall short of human performance.Unlike humans’ reusable theories, agents’ prose-based discoveries can degrade when context is compacted and memory is rewritten.Source: §1 · p. 1
  • 99.2% RHAE versus 58.7% for the same base model in its coding harness on ARC-AGI-3; Schema also solves all 21 public DiG-bench games and reaches the top-50 human median on MazeBench.The benchmark figure compares Schema with baseline harnesses using the same base models.Source: Figure 1 · p. 2, §1 · p. 2
  • Schema represents discovered environment mechanisms as executable programs that the agent checks against interaction history and uses to guide experimentation and planning.This keeps its understanding in a persistent, executable, and verifiable form.Source: §1 · p. 2
  • The paper presents interactive program induction, a Schema harness instantiating it, and ablation and behavioral analyses of mechanism discovery and sustained exploration.The analyses examine how Schema’s components support those capabilities.Source: §1 · p. 2

2 Preliminaries

The task setting concerns agents that must discover an unfamiliar environment’s rules and completion conditions through interaction. Program induction offers a way to infer executable models from observed input–output examples and revise them with counterexamples.

2 Preliminaries

  • Agents receive observations and choose actions while the unknown transition function and completion predicate define the environment’s mechanisms.The ordered interaction history records observations, actions, and resulting observations.Source: §2 · p. 2
  • The objective is to complete the task with as few environment interactions as possible, so actions both advance the task and provide evidence about its mechanisms.The passage motivates this objective by the cost of real-world experimentation or game rules.Source: §2 · p. 3
  • Program induction searches for an executable program consistent with input–output examples, while counterexamples constrain revised candidates without discarding collected evidence.For environment learning, action outcomes provide examples from which language models can induce programs describing dynamics.Source: §2 · p. 3

3 Schema: Agentic Harness with Interactive Program Induction

Schema combines program induction with action selection: an LLM agent maintains an executable model, checks it against past interactions, searches within it, and verifies actions against its predictions. The agent directs how these operations are used as it investigates and revises its model.

3 Schema: Agentic Harness with Interactive Program Induction

  • Interactive program induction integrates program induction and action selection, with Schema providing hypothesize, certify, plan, and act-with-verification operations.The agent chooses how to organize interface calls and can use its prior knowledge to guide interaction.Source: §3 · p. 3

3.1 Hypothesize: Encoding Mechanisms as Programs

  • The program represents observed objects, attributes, and relations in a structured state, then encodes action effects and object interactions as transition rules.The harness invokes the program through a common prediction interface; the agent revises its representation and rules while observed transitions are added to history.Source: §3.1 · p. 3

3.2 Certify: Checking Consistency with History

  • The harness replays recorded interactions under a candidate program and compares predicted with observed outcomes, including completion or failure feedback.Reported mismatches provide counterexamples for revision, and rechecking the full history tests revisions against previously explained behavior.Source: §3.2 · p. 3

3.3 Plan: Searching within the Program

  • The program serves as a simulator for searching toward agent-chosen targets, including task completion, waypoints, or situations that test unresolved mechanisms.The agent selects the search procedure and computational budget; the harness returns a candidate plan or reports that none was found within budget.Source: §3.3 · pp. 3–4

3.4 Act with Verification: Testing Predictions in the Environment

  • Committed action sequences are checked one step at a time, and the harness stops at the first prediction mismatch and returns the unexpected transition as new evidence.When prediction and observation agree, execution continues without another LLM call.Source: §3.4 · p. 4

4 Experiments

The experiments test Schema across model configurations, hidden-rule games, and long-horizon exploration, comparing it with baseline harnesses using the same base model. Results cover task performance, mechanism discovery, and whether learned knowledge remains compact and useful as interaction histories grow.

4.1 ARC-AGI-3: Human-level Action Efficiency

  • 99.2% RHAE with Fable 5, versus 58.7% in its coding harness; across four configurations, Schema reaches 86.1–99.2% RHAE and wins 22–25 games, compared with 1.2–20.2% and 0–6 in basic harnesses.With Fable 5, Schema completes all 25 games in fewer actions than the human baseline, using 57% of the human action total across 183 levels.Source: Figure 3 · p. 5, §4.1 · p. 5
  • Removing any tested Schema component reduces RHAE from 72.9% to 52.4–62.3% on the ten hardest games.The ablations replace the executable program with prose or remove certification, planning, or verified execution.Source: §4.1 · p. 5, Table 1 · p. 5
  • In CN04, explicit geometric constraints let Schema complete a level in 279 actions rather than the prose agent’s 1,219; in LS20, planning reduces actions from 233 to 65.Without certification, AR25 history agreement falls from 97.7% to 65.2%, while Schema’s final model reproduces 99.6% of its history; without verification, post-mismatch continuations account for 58% of actions across ten games.Source: §4.1 · p. 6, Figure 4 · p. 6

4.2 DiG-bench: Efficient Mechanism Discovery

  • $3.40 per cleared level for Schema versus $4.00 for the basic harness, while Schema clears 19, 20, and 21 games at medium, high, and maximum effort, compared with 11, 16, and 19.At medium effort, lives lost fall from 96 to 34; at maximum effort, the win rate on the two hardest tiers rises from 66.7% to 100%.Source: §4.2 · p. 7, Figure 6 · p. 7, Figure 5 · p. 7
  • Schema tests competing rule explanations after contradictory feedback and checks that revisions also account for earlier observations, resolving uncertainty before risking lives on untested answers.In P-3 level 3, it varies letter order and counts to discover an acceptance rule missed by the basic harness.Source: §4.2 · p. 7

4.3 MazeBench: Knowledge Accumulation over Long Horizons

  • Over 36 hours, Schema collects 33 gems and visits 139 rooms in 27,819 actions, exceeding the top-50 human median on both metrics.At 20,673 actions, Schema collects 30 gems and visits 133 rooms, compared with Codex’s 23 gems and 113 rooms at similar token cost.Source: §4.3 · p. 8, Figure 8 · p. 8
  • After action 10,000, Schema adds 38 rooms and 13 gems over the next 10,000 actions, compared with Codex’s 18 rooms and five gems; mean board-state novelty is 54% versus 40%.Both agents had visited 95 rooms by action 10,000.Source: §4.3 · p. 8, Figure 8 · p. 8
  • By about 20,000 actions, Schema’s program has 2,012 non-comment lines versus 6,133 prose notes, while transitions explained per line and function call sites increase and prediction accuracy remains high.Schema reuses an ice-sliding rule learned around action 2,600 in a new maze roughly 25,000 actions later, after at least 20 context compactions, and executes a 38-action A* route with every transition matching prediction.Source: §4.3 · pp. 8–9, Figure 9 · p. 8

5 Related Work

Related work studies agent harnesses that structure interaction and preserve learning, as well as executable world models and program-revision methods. Schema organizes these ideas around an agent-directed, evolving executable theory of the environment.

5 Related Work

  • Earlier harnesses structure interaction or turn feedback into reusable reflections and strategies; Schema instead organizes learning and action around one persistent executable theory, certified against interaction history and used for experimentation and planning.ReAct, CodeAct, SWE-agent, Reflexion, ACE, and self-improving systems provide the cited examples of these approaches.Source: §5 · p. 9

Code World Models.

  • Prior world-model methods use LLMs to synthesize or refine programs within predefined procedures and typically learn dynamics over supplied state representations, whereas Schema gives the agent control over revision, experimentation, and planning.Schema also lets the agent develop state grounding and task-goal understanding when these are initially unknown.Source: Code World Models · p. 9
  • Concurrent ARC-AGI-3 systems also combine executable modeling, interaction feedback, and planning, while this study explores interactive program induction across diverse unfamiliar environments.Source: Code World Models · p. 9

6 Conclusion

The conclusion presents interactive program induction as a way for agents to learn unfamiliar environments by constructing, testing, and using executable models. Related-work passages connect this approach to persistent knowledge representations and code world models while distinguishing Schema’s agent-directed control.

6 Conclusion

  • Across ARC-AGI-3, DiG-bench, and MazeBench, Schema improves task performance with frozen language models, and analyses show learned rules persisting across context compactions and being reused in new situations.The conclusion frames persistent executable models as a means of accumulating discoveries as explicit hypotheses that can be tested, refined, reused, and acted upon.Source: §6 · p. 9

A.1 Agent Harnesses and Knowledge Representation

  • Unlike representations that preserve history or reusable skills, Schema makes an evolving executable theory the persistent object: history checks it, and it supplies predictions for experiments and plans, including simulations of unseen situations.The program remains available across context compactions.Source: §A.1 · p. 16

A.2 Code World Models

  • Schema places LLM-based world modeling at the agent-architecture level: the agent controls theory revision, experience checks, investigation, and planning, including state grounding when representations and goals are initially unknown.The passage contrasts this with prior methods that use predefined learning procedures and typically supplied state representations.Source: §A.2 · p. 16

A.3 Program Induction and Active Experimentation

Prior work studies program synthesis and iterative refinement, as well as experimental design for collecting informative evidence. Schema connects program checking to ongoing interaction and uses a revisable theory for both experimentation and task planning.

A.3 Program Induction and Active Experimentation

  • Program-induction approaches construct, check, and reuse programs through input-output examples, partial programs constrained by counterexamples, or learned reusable components.Examples include programming-by-example, Sketching, and DreamCoder.Source: §A.3 · p. 17
  • Schema tests successive program revisions against recorded transitions, using prediction failures as evidence for further induction and replaying full history to check that repairs preserve earlier mechanisms.Source: §A.3 · p. 17
  • Schema lets the agent reach situations that test suspected mechanisms, compare outcomes with predictions, and incorporate evidence into the same theory used for task planning.This links experimentation and task progress to a shared, continually revised account of the environment.Source: §A.3 · p. 17

B Implementation Details

Schema gives the agent a persistent program workspace and tools to revise and check its model, plan within it, and execute actions with step-by-step verification.

B Implementation Details

  • The workspace preserves programs, notes, helper scripts, and interaction history across turns, levels, and context compactions, reconstructing the current state by replaying history under the current program.The agent can retrieve recorded transitions and revise representations, transition rules, and candidate programs.Source: B Implementation Details · p. 17
  • Backtesting replays recorded interactions to compare program predictions with observations, report mismatches, and test candidate programs before adoption.The agent can also inspect an individual action prediction before acting.Source: B Implementation Details · pp. 17–18
  • Planning searches rollouts of the program for an agent-selected target without consuming environment actions, returning an action sequence or feedback about exhaustion or budget limits.The agent can choose search procedures, candidate actions, computational budget, heuristics, and waypoints.Source: B Implementation Details · p. 18
  • Committed actions execute one at a time, with each observed transition checked against the program prediction; a mismatch drops the remaining actions and returns control to the agent.Matching predictions allow execution to continue without another LLM call.Source: B Implementation Details · p. 18
  • Benchmark adapters expose each environment’s native observations, actions, and feedback to the same program-revision, replay, planning, and verified-execution operations.ARC-AGI-3 uses grids, DiG-bench uses text, and MazeBench uses ASCII room renderings.Source: B Implementation Details · p. 18

C Benchmark Details

The section describes three benchmarks that test discovery and use of unknown rules, with distinct environments, task demands, and evaluation scopes.

C.1 ARC-AGI-3

  • ARC-AGI-3 evaluates visual games whose mechanics and objectives must be discovered, with successive levels recombining mechanics into harder puzzles.The evaluation covers all 25 public games (183 levels); the ablations use ten games (75 levels), and RHAE combines completion with action efficiency relative to first-time human play.Source: §C.1 · pp. 18–19, Figure 10 · p. 19

C.2 DiG-bench

  • DiG-bench contains 70 text games in which both transition rules and win conditions must be inferred, while limited lives and step budgets make informative experiments important.The experiments cover all 21 public games; the other 49 are held privately for evaluation.Source: §C.2 · p. 19, Table 3 · p. 20

C.3 MazeBench

  • MazeBench is a three-dimensional exploration and puzzle environment with 256 interconnected rooms and 100 gems, requiring mechanisms to be discovered and applied across distant rooms.The study uses its ASCII track; gems collected and rooms visited measure puzzle-solving and exploration over long interactions.Source: §C.3 · pp. 19–20, Figure 11 · p. 20, Table 4 · p. 21

D.1 ARC-AGI-3: Cases Behind the Ablations

Recorded cases illustrate how Schema’s representation, certification, planning, and verified execution address distinct challenges, alongside a DiG-bench example of learning a hidden string rule.

D.1 ARC-AGI-3: Cases Behind the Ablations

  • 279 actions versus 1,219 for the prose-model variant: Schema represents changing piece bodies and connectors separately, then searches arrangements that join all connectors without body overlap.After four growth actions, the piece has seven connectors and the final arrangement pairs all fourteen connectors into seven joints.Source: §D.1 · p. 22
  • 267/268 transitions (99.6%): certification leaves Schema’s final AR25 model consistent with nearly all recorded transitions despite revisions that otherwise damage earlier predictions.Without certification, agreement on the same sixteen transitions fell from 16/16 to 1/16, and the later program predicted a two-cell rather than one-cell reflection movement.Source: §D.1 · p. 22, Figure 13 · p. 22
  • 65 actions versus 233: planning helps Schema coordinate the player’s route, marker contact, symbol rotation, and remaining energy in LS20.The final thirteen-action plan begins with a down–up pair that rotates the carried symbol into the target shape; eleven actions then reach the goal.Source: §D.1 · p. 23, Figure 14 · p. 23
  • Without verified execution, a 43-action LS20 plan continued after its first prediction mismatch and exhausted energy after relying on a spent refill station.The agent revised its program only afterward to consume stations after use and require a still-present station for refueling.Source: §D.1 · p. 23, Figure 15 · p. 23

D.2 DiG-bench: Discovering a Hidden String Rule

  • In DiG-bench P-3, the agent replaces positional hypotheses with the rule s.count('a') > s.count('b') after practice queries distinguish letter counts from positions.Rearranging letters preserves acceptance, adding a second b removes it, and surrounding a with other letters preserves it.Source: §D.2 · p. 24, Table 6 · p. 24
  • All eight quiz strings are classified correctly without losing a life after the program reproduces all 107 checkable transitions collected during practice and earlier levels.Across the full game, the run clears all eight levels with one life lost; the basic harness at medium effort stops at levels 3, 4, and 5 in three runs.Source: §D.2 · p. 24, Table 7 · p. 24

D.3 MazeBench: Reusing a Rule After Long Interaction

A movement rule discovered in one MazeBench room remains usable after extensive interaction and supports planning in a later room.

D.3 MazeBench: Reusing a Rule After Long Interaction

  • At action 2,638, the revised program reproduces all 2,638 recorded transitions after adding and probing the ice-sliding rule discovered in IxG.Nine subsequent probes matched predictions, including a slide that ends on ordinary ground beyond the ice.Source: §D.3 · p. 25, Figure 16 · p. 25
  • In NxE, the program adds room geometry while all 58 top-level functions and classes remain unchanged, allowing the existing movement code to supply sliding consequences in the new layout.Schema enters NxE at action 27,486 and recovers the wall and ice geometry, including an ordinary entry tile initially hidden by the player.Source: §D.3 · p. 25
  • A* finds a 38-action route to the gem in NxE 24,852 actions after the IxG probes, and all 38 actions match saved forward predictions despite at least 35 context compactions.The final action collects the gem at action 27,528.Source: §D.3 · p. 25, Figure 16 · p. 25

E.1 ARC-AGI-3 Per-Game Results

These results report Schema’s level-clearance efficiency on ARC-AGI-3, repeated-run performance on DiG-bench, and room coverage on MazeBench.

E.1 ARC-AGI-3 Per-Game Results

  • Schema clears all 183 ARC-AGI-3 levels with Claude Fable 5 in 57% of human actions, and with GPT-5.6 Sol at maximum effort in 63%.It uses fewer actions than the human baseline on 163 levels with Claude Fable 5.Source: §E.1 · p. 26, Table 8 · p. 26, Figure 18 · p. 28

E.2 DiG-bench Repeated Runs

  • At medium effort, Schema wins 19.3 DiG-bench games on average versus 8.7 for the basic harness, already matching its maximum-effort result.Table 9 reports mean and standard deviation over three runs.Source: §E.2 · p. 31, Table 9 · p. 31, Figure 21 · p. 31
  • Across all efforts and runs, Schema wins 161 of 162 game runs in DiG-bench tiers 1–6 and 17 of 27 in tier 7, against five basic-harness tier-7 wins.The gains are concentrated in the hardest games.Source: §E.2 · p. 31, Figure 21 · p. 31, Figure 22 · p. 32

E.3 MazeBench Gem Collection and Room Coverage

  • Schema and Codex with GPT-6 Astra share 106 visited MazeBench rooms; 33 more appear only in Schema’s trajectory and seven only in Codex’s.Schema also reaches every room visited by either of the other two baselines.Source: §E.3 · p. 33, Figure 23 · p. 33
  • Table 10 lists 33 gems collected across 31 rooms; its action counts include camera changes, undo, reset, and room returns.Coordinates use unrotated top views, and each gem’s disappearance at collection helps recover its location.Source: Table 10 · p. 33, §E.3 · p. 33

Related papers

Loading 2609.39140v1…