A Markovian Framing of WaveFunctionCollapse for Procedurally Generating Aesthetically Complex Environments

• URL: http://arxiv.org/abs/2509.09919v2
• Date: Mon, 20 Oct 2025 00:47:57 GMT
• Title: A Markovian Framing of WaveFunctionCollapse for Procedurally Generating Aesthetically Complex Environments
• Authors: Franklin Yiu, Mohan Lu, Nina Li, Kevin Joseph, Tianxu Zhang, Julian Togelius, Timothy Merino, Sam Earle,
• Abstract summary: Procedural content generation often requires satisfying both designer-specified objectives and adjacency constraints implicitly imposed by the underlying tile set.<n>We reformulate WaveFunctionCol (WFC) as a Markov Decision Process (MDP)<n>We find that joint optimization not only struggles as task complexity increases, but consistently underperforms relative to optimization over the WFC-MDP.
• Score: 5.114029940159893
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Procedural content generation often requires satisfying both designer-specified objectives and adjacency constraints implicitly imposed by the underlying tile set. To address the challenges of jointly optimizing both constraints and objectives, we reformulate WaveFunctionCollapse (WFC) as a Markov Decision Process (MDP), enabling external optimization algorithms to focus exclusively on objective maximization while leveraging WFC's propagation mechanism to enforce constraint satisfaction. We empirically compare optimizing this MDP to traditional evolutionary approaches that jointly optimize global metrics and local tile placement. Across multiple domains with various difficulties, we find that joint optimization not only struggles as task complexity increases, but consistently underperforms relative to optimization over the WFC-MDP, underscoring the advantages of decoupling local constraint satisfaction from global objective optimization.

Related papers

• Multi-Objective Hierarchical Optimization with Large Language Models [41.41567058185742]
  Large Language Models (LLMs) are not the off-the-shelf choice to drive multi-objective optimization yet.<n>In this paper, we close this gap by leveraging LLMs as surrogate models and candidate samplers inside a structured hierarchical search strategy.
  arXiv  Detail & Related papers  (2026-01-20T12:10:13Z)
• MAESTRO: Meta-learning Adaptive Estimation of Scalarization Trade-offs for Reward Optimization [56.074760766965085]
  Group-Relative Policy Optimization has emerged as an efficient paradigm for aligning Large Language Models (LLMs)<n>We propose MAESTRO, which treats reward scalarization as a dynamic latent policy, leveraging the model's terminal hidden states as a semantic bottleneck.<n>We formulate this as a contextual bandit problem within a bi-level optimization framework, where a lightweight Conductor network co-evolves with the policy by utilizing group-relative advantages as a meta-reward signal.
  arXiv  Detail & Related papers  (2026-01-12T05:02:48Z)
• UCPO: A Universal Constrained Combinatorial Optimization Method via Preference Optimization [20.001544937354577]
  Universal Constrained Preference Optimization (UCPO) is a novel plug-and-play framework that seamlessly integrates preference learning into existing neural solvers.<n>UCPO embeds constraint satisfaction directly into a preference-based objective.<n>It achieves exceptional performance with as little as 1% of the original training budget.
  arXiv  Detail & Related papers  (2025-11-13T10:03:53Z)
• LLM4CMO: Large Language Model-aided Algorithm Design for Constrained Multiobjective Optimization [54.83882149157548]
  Large language models (LLMs) offer new opportunities for assisting with algorithm design.<n>We propose LLM4CMO, a novel CMOEA based on a dual-population, two-stage framework.<n>LLMs can serve as efficient co-designers in the development of complex evolutionary optimization algorithms.
  arXiv  Detail & Related papers  (2025-08-16T02:00:57Z)
• Scalable Min-Max Optimization via Primal-Dual Exact Pareto Optimization [66.51747366239299]
  We propose a smooth variant of the min-max problem based on the augmented Lagrangian.<n>The proposed algorithm scales better with the number of objectives than subgradient-based strategies.
  arXiv  Detail & Related papers  (2025-03-16T11:05:51Z)
• SparseLLM: Towards Global Pruning for Pre-trained Language Models [12.057369029549534]
  We propose SparseLLM, a novel framework that redefines the global pruning process into manageable, coordinated subproblems. SparseLLM's approach conceptualizes LLMs as a chain of modular functions and leverages auxiliary variables for problem decomposition. It demonstrates significant performance improvements, particularly in high-sparsity regimes.
  arXiv  Detail & Related papers  (2024-02-28T00:09:07Z)
• Dynamic Regularized Sharpness Aware Minimization in Federated Learning: Approaching Global Consistency and Smooth Landscape [59.841889495864386]
  In federated learning (FL), a cluster of local clients are chaired under the coordination of a global server. Clients are prone to overfit into their own optima, which extremely deviates from the global objective. ttfamily FedSMOO adopts a dynamic regularizer to guarantee the local optima towards the global objective. Our theoretical analysis indicates that ttfamily FedSMOO achieves fast $mathcalO (1/T)$ convergence rate with low bound generalization.
  arXiv  Detail & Related papers  (2023-05-19T10:47:44Z)
• Accelerated Federated Learning with Decoupled Adaptive Optimization [53.230515878096426]
  federated learning (FL) framework enables clients to collaboratively learn a shared model while keeping privacy of training data on clients. Recently, many iterations efforts have been made to generalize centralized adaptive optimization methods, such as SGDM, Adam, AdaGrad, etc., to federated settings. This work aims to develop novel adaptive optimization methods for FL from the perspective of dynamics of ordinary differential equations (ODEs)
  arXiv  Detail & Related papers  (2022-07-14T22:46:43Z)
• Disentangled Federated Learning for Tackling Attributes Skew via Invariant Aggregation and Diversity Transferring [104.19414150171472]
  Attributes skews the current federated learning (FL) frameworks from consistent optimization directions among the clients. We propose disentangled federated learning (DFL) to disentangle the domain-specific and cross-invariant attributes into two complementary branches. Experiments verify that DFL facilitates FL with higher performance, better interpretability, and faster convergence rate, compared with SOTA FL methods.
  arXiv  Detail & Related papers  (2022-06-14T13:12:12Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.