# Schema: Discovering Unknown Environments via Agentic Program Induction

arXiv: https://arxiv.org/abs/2609.39140 · HTML: https://mlsanity.com/paper/2609.39140/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in General LLM agent frameworks and benchmarks, one of 16 directions in LLM agents and tool use.
- Builds on 47 of its 75 references that are in the map.
- First posted on arXiv 30 Sep 2026.

## Placed in

- LLM agents and tool use / [General LLM agent frameworks and benchmarks](https://mlsanity.com/agents/general-llm-agent-frameworks-and-benchmarks/)

## Builds on (most cited first, 30 of 47)

- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [Lost in the Middle: How Language Models Use Long Contexts](https://mlsanity.com/paper/2307.03172/) (2023)
- [SWE-bench: Can Language Models Resolve Real-World GitHub Issues?](https://mlsanity.com/paper/2310.06770/) (2023)
- [Voyager: An Open-Ended Embodied Agent with Large Language Models](https://mlsanity.com/paper/2305.16291/) (2023)
- [SWE-agent: Agent-Computer Interfaces Enable Automated Software Engineering](https://mlsanity.com/paper/2405.15793/) (2024)
- [τ-bench: A Benchmark for Tool-Agent-User Interaction in Real-World Domains](https://mlsanity.com/paper/2406.12045/) (2024)
- [MemGPT: Towards LLMs as Operating Systems](https://mlsanity.com/paper/2310.08560/) (2023)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [OSWorld: Benchmarking Multimodal Agents for Open-Ended Tasks in Real Computer Environments](https://mlsanity.com/paper/2404.07972/) (2024)
- [DeepSeek-V4: Towards Highly Efficient Million-Token Context Intelligence](https://mlsanity.com/paper/2606.19348/) (2026)
- [Terminal-Bench: Benchmarking Agents on Hard, Realistic Tasks in Command Line Interfaces](https://mlsanity.com/paper/2601.11868/) (2026)
- [Executable Code Actions Elicit Better LLM Agents](https://mlsanity.com/paper/2402.01030/) (2024)
- [MLE-bench: Evaluating Machine Learning Agents on Machine Learning Engineering](https://mlsanity.com/paper/2410.07095/) (2024)
- [LLMs Get Lost In Multi-Turn Conversation](https://mlsanity.com/paper/2505.06120/) (2025)
- [Agentic Context Engineering: Evolving Contexts for Self-Improving Language Models](https://mlsanity.com/paper/2510.04618/) (2025)
- [Darwin Godel Machine: Open-Ended Evolution of Self-Improving Agents](https://mlsanity.com/paper/2505.22954/) (2025)
- [Measuring AI Ability to Complete Long Software Tasks](https://mlsanity.com/paper/2503.14499/) (2025)
- [BALROG: Benchmarking Agentic LLM and VLM Reasoning On Games](https://mlsanity.com/paper/2411.13543/) (2024)
- [Hypothesis Search: Inductive Reasoning with Language Models](https://mlsanity.com/paper/2309.05660/) (2023)
- [Competitive Programming with Large Reasoning Models](https://mlsanity.com/paper/2502.06807/) (2025)
- [WorldCoder, a Model-Based LLM Agent: Building World Models by Writing Code and Interacting with the Environment](https://mlsanity.com/paper/2402.12275/) (2024)
- [Phenomenal Yet Puzzling: Testing Inductive Reasoning Capabilities of Language Models with Hypothesis Refinement](https://mlsanity.com/paper/2310.08559/) (2023)
- [Vending-Bench: A Benchmark for Long-Term Coherence of Autonomous Agents](https://mlsanity.com/paper/2502.15840/) (2025)
- [Human-Level Reinforcement Learning through Theory-Based Modeling, Exploration, and Planning](https://mlsanity.com/paper/2107.12544/) (2021)
- [Generating Code World Models with Large Language Models Guided by Monte Carlo Tree Search](https://mlsanity.com/paper/2405.15383/) (2024)
- [Investigating Human Priors for Playing Video Games](https://mlsanity.com/paper/1802.10217/) (2018)
- [ARC-AGI-3: A New Challenge for Frontier Agentic Intelligence](https://mlsanity.com/paper/2603.24621/) (2026)
- [Why Do LLM Agents Fail in Exploring New Environments? A World-Modeling Perspective](https://mlsanity.com/paper/2510.15047/) (2025)
- [PoE-World: Compositional World Modeling with Products of Programmatic Experts](https://mlsanity.com/paper/2505.10819/) (2025)

## Abstract (arXiv)

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.