TL;DR
Researchers have developed a framework that uses Large Language Models (LLMs) to evolve complex, code-based policies for long-horizon tasks without requiring any LLM calls at runtime. By using a "feedback cascade" that prioritizes the state an agent is left in after a subgoal (continuation value) rather than just success, they boosted success rates in the survival game Craftax from near-zero to over 50%, eventually distilling this knowledge into a reusable "goal compiler."
What Problem Does This Paper Address?
Coding agents are increasingly used to synthesize control programs for robots or game agents. This "neuro-symbolic" approach is great because code is cheap to run and easy to audit compared to a neural network. However, two major hurdles remain:
- The Subgoal Trap: In long-horizon tasks (like a 100,000-action survival game), a local improvement—like learning to find food faster—might actually hurt the agent in the long run if it leaves the agent in a poor state (e.g., far away from the next objective or with depleted resources).
- The Synthesis Tax: Every time you give the agent a new goal, you usually have to run an expensive LLM synthesis process from scratch.
The authors tackle these by asking: How can we provide feedback that actually helps an LLM optimize for the "endgame," and how can we turn a single-task policy into a reusable tool for any future goal?
Methods
The framework operates in two distinct stages:
Stage 1: The Feedback Cascade
Instead of just telling the LLM "you died" or "you won," the authors use a Feedback Cascade (A-E). This progressively moves from coarse to dense feedback:
- Episode Outcomes: Simple win/loss.
- Per-milestone Pass Rates: Scoring progress through game levels.
- Save-state Branching: Restarting from a "checkpoint" to see if a code edit improves the chance of reaching the final boss from that specific point.
- Continuation Value: This is the "secret sauce." It measures not just if a subgoal was completed, but the probability of winning the entire game given the state the agent is in after that subgoal.
- Model Audits: Checking the accuracy of the agent's internal "beliefs" (e.g., predicting enemy cooldowns).
Stage 2: Policy Factorization and Goal Compilation
Once they have a "master" policy, they factor it into two parts:
- The Machine ($I$): A fixed C++ library containing the "muscles" and "senses" (navigation, combat skills, spatial memory).
- The Rule Program ($p_0$): A high-level strategy written in a "teleo-reactive" rule language.
They then use an LLM to write a Goal Compiler ($C_\theta$). This is a Python script that takes a new, structured goal (e.g., "get 6 coal while keeping 2 iron") and automatically emits the specific rules needed to achieve it, leveraging the pre-trained "Machine."
Datasets
The primary benchmark is Craftax (Matthews et al. 2024), a procedurally generated survival game inspired by NetHack and Minecraft. It requires agents to manage hunger, thirst, and health while descending through eight increasingly difficult levels to defeat a final boss. The authors used a C-language version of the environment for high-performance simulation.
Key Insights and Ideas
- Subgoal success is a misleading metric. The paper finds that an edit's effect on reaching the next level is often negatively correlated with reaching the final level. This highlights why "continuation-based feedback" is essential: it forces the LLM to value "sustainable" success.
- The LLM as a Compiler, not a Controller. By moving the LLM to the "development" phase and using it to build a compiler, the system achieves zero-shot transfer to new tasks. The agent acts instantly at runtime because it's just running compiled C++ code, not waiting for a model inference.
- Neuro-Symbolic Division of Labor. The LLM handles the "creative" search for strategy, while the symbolic code handles the "reliable" execution. This allows for a 4.9x speedup over the original unoptimized C code.
Key Results
- Massive Success Boost: Policies optimized with simple episode-level feedback stalled at a 0.29% success rate for reaching the final floor. The feedback cascade pushed this to 50.49%, with a 28% final boss defeat rate.
- Zero-Shot Generalization: The goal compiler, trained only on short tasks (2–4 stages), successfully completed 71.3% of unseen, longer tasks (up to 8 stages). This significantly outperformed baseline "guards" (36.2%) that only enforced resource constraints.
- Efficiency: A single shared compiler search "pays for itself" after just eight tasks compared to running a fresh LLM search for every new objective.
Limitations and Future Work
- Domain Specificity: The "Machine" ($I$) is currently Craftax-specific. While the framework is general, the low-level skills were evolved specifically for this game.
- Lineage Dependence: The feedback regimes were introduced manually by the researchers when they noticed the LLM plateauing. Automating the transition between feedback stages is a logical next step.
- Restricted Goal Language: The compiler currently works with a specific structured goal language. Expanding this to handle natural language instructions directly would increase usability.
For more details, you can find the code at github.com/vicgalle/craftax-program-policies.
Summary updated