PaperlayerView exact revision on arXiv

Source-linked AI summary

Procedural Content Metageneration via Program Search and Continual Abstraction Discovery

Matthew Siper, Ahmed Khalifa, Julian Togelius

arXiv:2608.17947v1cs.AIcs.LGcs.NE

TL;DR

Procedural content metageneration seeks to automate the costly creation of game-specific generators by searching over generators rather than individual levels. This paper introduces Continual Abstraction Discovery, which extracts and reuses validated primitives during LLM-driven evolutionary program search, and finds higher mean final best fitness across four game domains with and without fixed helper APIs.

  • Problem

    Procedural content metageneration needs reusable search primitives because raw-code search can repeatedly recreate useful routines while fixed helper APIs cannot expand their vocabulary.

  • Method

    Continual Abstraction Discovery extracts, validates, and reuses utilities from high-fitness programs in a run-specific helper module during evolutionary program search.

  • Results

    CAD raises mean final best fitness across Sokoban, Zelda, Dangerous Dave, and Lode Runner whether runs start with empty or expert helper functions.

  • Takeaways & Limitations

    Learned libraries are adopted by later programs and repeatedly recover validation, reachability, and structural utilities, supporting adaptation of the searchable program vocabulary.

  • Takeaways & Limitations

    The approach has substantial compute costs, with typical 50-generation runs using millions of tokens and several hours of wall-clock time.

Abstract

from arXiv · show

Large language models can generate executable programs, which makes it possible to search directly over procedural content generators rather than individual levels. We study this approach in Sokoban, Zelda, Dangerous Dave, and Lode Runner. Each run evolves complete Python generators through language-model mutation and crossover. We introduce Continual Abstraction Discovery, or CAD, which extracts reusable primitives from high-fitness programs into a run-specific helper module. A 2x2 experiment crosses CAD with access to a fixed hand-written domain API. The completed data set contains 160 complete runs, with at least ten 50-generation runs in every cell. CAD raises mean final best fitness in all eight domain and API comparisons. Across all CAD runs, learned libraries are adopted by most later programs and repeatedly rediscover validation, reachability, and structural utilities. These results support that discovering reusable primitives improves evolutionary program search for content generators.

I. Introduction

The paper frames procedural content metageneration as searching for executable game generators rather than individual artifacts, using LLM-driven evolutionary program search. It introduces Continual Abstraction Discovery (CAD), which learns reusable utilities during search, and evaluates CAD against a fixed helper API across four game domains.

  • Motivation: Procedural content metageneration searches for generators themselves rather than individual artifacts, addressing the engineering and repeated evaluation required by custom game-specific generators.Existing approaches include evolutionary computation, machine learning, and reinforcement learning, while many produce opaque representations.
  • Approach: LLM-driven evolutionary search executes candidate programs, evaluates their generated levels, and uses feedback to guide later mutation and crossover.Executable source code can be compiled, tested, modified by designers, and reused outside the search system.
  • Problem and solution: Raw-code search can independently recreate useful routines, whereas a hand-written helper API exposes reusable operations but cannot expand its vocabulary during search.CAD addresses this limitation by allowing the set of executable primitives to increase during a run.
  • Contribution: CAD improves evolutionary generator search by extracting, validating, and reusing helper functions discovered in high-fitness programs.The learned utilities are stored in a run-specific helper module and used when programs can be safely refactored.
  • Experimental design: The main study crosses CAD with access to a fixed expert helper API, separating reusable vocabulary access from vocabulary discovery during search.The study comprises a 2 × 2 design across 160 completed runs.
  • Results: Positive CAD effects appear across Sokoban, Zelda, Dangerous Dave, and Lode Runner, alongside analysis of learned-library growth, adoption, and primitives.The evaluation uses executable Python-level generators and reports effects across all four game domains.

II. Related Work

Prior work spans computational, learning-based, and evolutionary approaches to game-content generation, but specialized constructive or black-box generators limit reuse and interpretability. LLM-based level generation remains mixed and struggles with spatial and structural constraints, motivating CAD as a search-time abstraction mechanism.

  • Computational game-content generation: Evolutionary computation, constraint satisfaction, supervised learning, and reinforcement learning have all been applied to game-content generation, while constructive generators are typically game-specific and difficult to reuse.The passage surveys diverse generation paradigms and identifies specialization as a limitation of published-game generators.
  • LLM limitations: LLMs struggle with spatial and structural level constraints, including guaranteed paths and matching quantities such as doors and keys, reflecting weak spatial reasoning,, [18].These failures include enforcing exactly one player and equal numbers of doors and keys.
  • Evolutionary program synthesis: LLM code generation inside a fitness-guided evolutionary loop connects this work to genetic programming,, where the LLM performs mutation and crossover.The approach is useful when the desired behavior can be specified by a fitness function even if the implementation is unknown.
  • Continual abstraction discovery: Unlike agent skill libraries such as Voyager’s Minecraft library [24], CAD continually extracts helper functions from high-performing generators and changes the primitives available during ongoing search.CAD is therefore a search-time representation mechanism rather than a record of solved tasks or manually exposed skills.
  • Representation in PCG: Machine-learning PCG commonly learns opaque neural or black-box generators, whereas evolutionary approaches can learn symbolic generators that support greater human interpretation and editing,.This contrast situates CAD within efforts to retain program-level structure rather than only black-box representations.

III. Method … C. Evaluation and Fitness

The method evolves complete executable Python generators through archive-based LLM mutation and crossover, while evaluating each candidate on validity, quality, and diversity. A robustness pipeline and run-level reflection memory support reliable iterative search.

  • A. Program Representation: Each candidate is a complete Python program with a fixed generate(context_dict) interface, allowing uniform compilation, execution, inspection, and evaluation.Programs receive grid dimensions and an initial level, then return a tile grid while retaining local functions, constants, and layout routines.
  • A. Program Representation: All runs start from one minimal seed program, and the archive retains every successfully evaluated individual.The seed contains tile constants and a blank or copied initial grid without generation logic.
  • B. Evolutionary Search: Each generation samples parents from the archive with fitness-proportional probability, using crossover with probability 0.25 when at least two individuals exist.Fitness values are floored at 10^-6 before normalization, and failed crossover attempts fall back to mutation.
  • B. Evolutionary Search: An LLM performs mutation and crossover using parent programs, domain information, run memory, and the fixed generator contract.Mutation requests a strong behavioral edit, whereas crossover combines compatible mechanisms into one executable program.
  • B. Evolutionary Search: Every candidate undergoes compilation and smoke testing, with error-conditioned correction attempts and zero fitness assigned when no valid candidate emerges.A program must complete at least three of five smoke tests; each mutation or crossover cycle is attempted up to four times, with failure types logged separately.
  • B. Evolutionary Search: After each generation, an LLM reflection call records changes, outcomes, and global lessons in per-run memory for subsequent search.Later mutation and crossover prompts receive accumulated global lessons instead of raw per-parent evaluation feedback.
  • C. Evaluation and Fitness: Fitness averages validity, benchmark quality, and pairwise diversity across 30 executions, using the PCG Benchmark functions and assigning zero to crashes or validation failures.The terms V, Q, and D lie in [0, 1], and fitness is defined as 3(V + Q + D).

D. Continual Abstraction Discovery · IV. Experimental Design · A. Domains

The study continually extracts tested utility functions from high-fitness programs and evaluates generators across four tile-based PCG Benchmark domains using quality, diversity, and a two-second execution limit.

  • D. Continual Abstraction Discovery: At generation 8 and every five generations thereafter, the system extracts reusable utilities from within-run programs at or above the 75th fitness percentile.Each proposed function must compile and pass a smoke test, with up to two compile corrections before refactoring.
  • D. Continual Abstraction Discovery: Accepted refactors are re-evaluated, archive entries are updated, and extracted functions become available through a system library during evolution.Refactoring is disabled when its success rate remains below 30% after a ten-generation warmup.
  • IV. Experimental Design: The experiments evaluate four tile-based domains from the PCG Benchmark.The domains are Sokoban, Zelda, Dangerous Dave, and Lode Runner.
  • A. Domains: Sokoban uses 5x5 levels where the player pushes boxes to designated target locations.This domain is described as a Japanese puzzle game.
  • A. Domains: Zelda uses 7x11 dungeon-crawler levels in which the player must obtain a key and reach the exit without being killed by monsters.The domain is inspired by dungeon rooms from the original The Legend of Zelda game.
  • A. Domains: Dangerous Dave uses 7x11 platformer levels where the player must obtain a key and reach the goal without being killed by spikes.The domain is based on the game with the same name.
  • A. Domains: Lode Runner uses 11x16 puzzle-platformer levels requiring players to collect all gold while avoiding enemies without jumping.Navigation uses walking, digging, ladders, and ropes; quality and diversity rely on framework outputs, including an A∗ solver, and each generator call is limited to two seconds.

B. Factorial Conditions · C. LLM and Execution Configuration

The study uses a factorial design to test CAD and a hand-designed Expert API as sources of helper functions, while holding the remaining search pipeline constant. All runs use GLM 5.2 with specified generation settings and documented computational costs.

  • B. Factorial Conditions: The main study comprises four experiments crossing CAD with access to an Expert API to test the usefulness of helper functions.CAD allows the LLM to abstract programs and generate helper functions.
  • B. Factorial Conditions: CAD lets the LLM abstract programs and generate reusable helper functions during the search.This condition follows the abstraction procedure described in section III-D.
  • B. Factorial Conditions: The Expert API supplies hand-designed primitives for entity normalization, reachability, repair, and domain-specific structural operations.Examples include connect_floors_with_ladder and ensure_one_player.
  • B. Factorial Conditions: The Expert API tests whether providing helper functions alone is sufficient or whether CAD remains necessary.Every experiment uses the same minimal seed, evolutionary search, reflection memory, correction pipeline, and evaluation settings.
  • C. LLM and Execution Configuration: All language-model calls use GLM 5.2, with temperature 0.2 for mutations and 0.1 for correction and refactoring.These settings define the language-model and execution configuration for the experiments.
  • C. LLM and Execution Configuration: A mean 50-generation run used approximately 9.5 million input tokens, 2.6 million output tokens, cost approximately $25, and took approximately 2.5 hours.Each run stores generation statistics, program sources, evaluation analyses, prompts, valid rendered levels, the evolution tree, reflection memory, and CAD helper-module snapshots.

V. Results · A. Cross-Domain Search Performance · B. Learned-Library Growth and Adoption

CAD improves endpoint search performance across all four domains, with an exact two-sided sign-test result of p = 0.008. Learned libraries expand early, stabilize across domains, and are adopted by most later programs while reducing best-program length in the Base condition.

  • A. Cross-Domain Search Performance: Under the fixed API, Lode Runner has the largest CAD–no-CAD separation, whereas the Base contrast is small in Lode Runner and larger in Sokoban.
  • A. Cross-Domain Search Performance: Only in Zelda does a predefined API outperform starting without an API, which the authors attribute to the problem’s simplicity.
  • A. Cross-Domain Search Performance: Representative levels show lower visual diversity with CAD, especially in Dangerous Dave, because its diversity metric tracks player-solution trajectories rather than visual appearance.The figure’s images illustrate output structure, while playability is evaluated through benchmark execution.
  • B. Learned-Library Growth and Adoption: Learned libraries expand sharply during early extraction cycles and then stabilize across all four domains.
  • B. Learned-Library Growth and Adoption: After helper use begins, adoption remains above roughly 80% for most later generations, with programs averaging approximately 15 to 20 helper calls.
  • B. Learned-Library Growth and Adoption: In the Base condition, CAD reduces the mean length of the best program from roughly 370 lines to roughly 296 lines.
  • A. Cross-Domain Search Performance: CAD produces a positive endpoint difference in every domain, with all experiments favoring CAD and an exact two-sided sign-test result of p = 0.008.The largest fixed-API separation occurs in Lode Runner, where CAD continues improving while no CAD plateaus earlier.

C. Repeated Abstraction Discovery … B. CAD as Representation Adaptation

Across four games, CAD improves mean fitness in every domain, with the largest effect in Lode Runner with the expert API. It discovers a recurring core of reusable generator operations while adapting libraries and representations to each run.

  • C. Repeated Abstraction Discovery: CAD repeatedly discovers validation, reachability, and structural operations while also producing a large tail of run-specific utilities.in_bounds and Entity Count Normalization each appear in 28 CAD runs; Ensure One Player and Grounded Empty Cells appear in 24.
  • C. Repeated Abstraction Discovery: CAD adapts generated levels by abstracting difficulty-increasing primitives, including placing enemies beside gold or around solution paths.Figure 5 also shows primitives for placing enemies beside gold in Lode Runner and away from Zelda’s player-key-door critical path.
  • A. Cross-Domain Evidence: CAD improves mean fitness in all four domains, with its largest effect in Lode Runner when the expert API is available; the other three API comparisons favor CAD without p < 0.05 tests.Even when domain-specific callable routines are already available, the run-specific learned vocabulary improves best fitness.
  • B. CAD as Representation Adaptation: The learned helper vocabulary is adopted by later programs and repeatedly addresses entity normalization, player placement, reachability, connectivity, and structural construction.CAD changes the operations available to later variation calls while retaining Python as the executable substrate.
  • B. CAD as Representation Adaptation: The learned library combines a recurring core with domain- and history-shaped utilities rather than converging to one fixed library.This recurring-core-plus-tail structure is described as characteristic of CAD’s adaptation across tile-based generator searches.
  • B. CAD as Representation Adaptation: CAD shortens the best Base programs, whereas the fixed API already produces compact source libraries.Figure 4 compares best-solution line counts under Base and API prompting with and without CAD.
  • VI. Discussion: Shorter programs are not shown to be intrinsically better; reusable callable vocabularies instead offload logic from generators, potentially easing later edits and preservation.The interpretation concerns expressiveness and maintainability rather than program length alone.

C. Practical Implications and Limitations · VII. Conclusion

The study finds that Continual Abstraction Discovery improves evolutionary program search across four procedural-content domains, while practical use remains constrained by evaluation gaps, substantial compute costs, and unisolated pipeline components.

  • C. Practical Implications and Limitations: Solvability, benchmark quality, and diversity do not fully capture visual style, pacing, novelty, or designer intent.Human review remains important when desired aesthetic or experiential goals are absent from the benchmark.
  • C. Practical Implications and Limitations: A typical 50-generation run uses millions of near-frontier-model tokens and several hours of wall-clock time, while CAD adds extraction, correction, and refactoring calls.Future work should evaluate fitness gains against token use and wall-clock cost.
  • C. Practical Implications and Limitations: CAD is evaluated as a complete pipeline, so helper extraction, module correction, and source refactoring lack separate ablations.Mechanism traces show growth, adoption, and program-size changes but do not isolate each component’s causal contribution.
  • C. Practical Implications and Limitations: Future studies should test longer budgets, other language models, non-tile content, cross-run library transfer, and designer editing of discovered helpers.These directions address both generality and human control of the discovered abstractions.
  • VII. Conclusion: Continual Abstraction Discovery raises mean final best fitness across Sokoban, Zelda, Dangerous Dave, and Lode Runner, with either empty or expert helper libraries.Each domain is evaluated across 10 runs.
  • VII. Conclusion: Learned libraries grow, are adopted by later programs, and repeatedly recover validation, reachability, and structural utilities.These findings support CAD as a mechanism for adapting the searchable program vocabulary during procedural content metageneration.

Appendix

The appendix documents the prompts and runtime conditions supporting evolutionary variation, error correction, memory reflection, and CAD helper-module maintenance. These prompts specify program contracts, feedback, reusable utilities, and recovery procedures across the search loop.

  • Mutation: The mutation prompt defines the generate(context_dict) contract, domain constraints, run memory, helper APIs, mutation strength, and parent-program input.It is shown as Fig. 6.
  • Variation and correction: Crossover combines two parent programs into a complete child, while correction prompts repair outputs that fail compilation or smoke testing.Crossover occurs with ∼25% probability when the archive has at least two agents; correction allows up to three retries.
  • Memory Reflection: Memory reflection runs after every generation, recording structured generation observations and updating global learnings for later variation calls.The memory includes parent and child fitness, evaluation feedback, failures, learned lessons, and code structure.
  • CL Helper Extraction: CAD extracts reusable domain utilities every five generations from generation 8 onward, using one call per high-fitness program in the window.This extraction prompt applies only to CL conditions and targets programs in the top fitness quartile.
  • CAD helper maintenance: CAD also corrects failed helper modules, refactors generators to call tested helpers, and scaffolds missing imported functions.These recovery and maintenance prompts apply only to CL conditions; refactoring follows mutation or crossover with 25% probability when helpers exist.
Loading 2608.17947v1…