Reward Prediction with Factorized World States

Yijun Shen, Delong Chen, Xianming Hu, Jiaming Mi, Hongbo Zhao, Kai Zhang, Pascale FungarXiv 2026 · arXiv

TL;DR

This paper introduces StateFactory, a zero-shot reward prediction framework that uses large language models (LLMs) to factorize unstructured text observations into structured, hierarchical object-attribute representations. By computing rewards as the continuous semantic distance between these factorized states and dynamically updated goals, StateFactory achieves exceptional generalization across unseen domains without explicit training. The authors also introduce RewardPrediction, a fine-grained benchmark dataset spanning five distinct text environments to rigorously evaluate step-wise task progress.

What Problem Does This Paper Address?

To effectively plan and execute multi-step tasks, autonomous agents require a reliable reward signal that measures how close they are to achieving their goal. Traditionally, researchers train supervised reward models on task-specific data. However, these models suffer from a severe generalization bottleneck: they tend to overfit to domain-specific surface patterns, causing their error rates to skyrocket when introduced to novel environments.

An alternative is to compute the semantic distance between the agent's current state and the goal state. While this works well in visual domains, extending it to high-level, language-based agent planning introduces two major bottlenecks:

  1. Unstructured Text Noise: Raw textual observations contain excessive distractors and "entangled attributes" (e.g., tracking an object's location change becomes difficult if its color or other static properties dilute the text embedding).
  2. Lack of Fine-Grained Benchmarks: Existing text-agent datasets primarily focus on sparse, outcome-oriented rewards (success/failure), making it difficult to systematically evaluate step-wise proximity to a goal.

Methods

The authors propose StateFactory, a representation-based framework that avoids direct reward regression by decomposing the problem into three integrated layers:

  1. State Extraction: A recurrent, goal-conditioned process where an LLM distills raw text observations into a structured JSON format that separates object identities from their evolving attributes (e.g., tracking a Mug with attributes like location: on the table and filled: empty).
  2. Goal Interpretation: Instead of keeping the goal static, StateFactory treats goal interpretation as an iterative, state-aware process that updates the goal state based on interaction history, preventing the "illusion of progress" caused by environmental changes.
  3. Hierarchical Routing: The final scalar reward is calculated by structurally aligning the extracted state and interpreted goal. It performs Object Matching (ensuring identity consistency) followed by Attribute Matching (averaging the semantic similarity of aligned attribute values using a text encoder like all-MiniLM-L6-v2).
StateFactory Framework Overview

This approach transforms reward estimation from a volatile, discrete text-generation task (like standard LLM-as-a-Judge prompting) into a continuous, robust semantic distance calculation.

Datasets

To evaluate reward quality, the authors introduced the RewardPrediction benchmark. It comprises 2,454 unique action-observation trajectories featuring step-wise ground-truth rewards across five diverse text-based environments:

  • AlfWorld: Embodied household instruction following (672 trajectories).
  • ScienceWorld: Elementary science experiments requiring complex causal reasoning (382 trajectories).
  • TextWorld: Procedural text-adventure games with lock-and-key puzzles (300 trajectories).
  • WebShop: E-commerce website navigation based on real Amazon data (600 trajectories).
  • BlocksWorld: Classical spatial planning and block stacking (500 trajectories).

Trajectories are structured as positive-negative pairs to force models to distinguish meaningful semantic progress from stochastic noise within the same task context. For the supervised baseline models, the authors scaled up data generation to approximately 350,000 trajectories.

Figure 2. RewardPrediction Benchmark Overview. Representative trajectories across five diverse domains. Each column displays a task instance with actions, observations, and the corresponding ground-truth task progress score (𝑅∈[0, 1]) at key time steps.

Key Insights and Ideas

  • The Supervised Overfitting Trap: Supervised reward models exhibit a staggering 138% average increase in reward prediction error when evaluated on novel domains, confirming they fail to learn a generalized concept of task progress.
  • Granularity is Crucial: Moving from raw observations to flat text states helps filter noise, but object-centric groupings still hit a precision ceiling due to attribute entanglement. Full factorization into minimal object-attribute units is required to eliminate semantic interference.
  • "Thinking" Boosts Factorization: Utilizing LLM backbones with native reasoning or "thinking" capabilities (e.g., reasoning-enhanced models) significantly improves the precision of state factorization compared to standard instruction-tuned models.
  • Embedding Discriminability Correlates with Performance: The accuracy of the framework is tightly bound to the underlying text embedding model's ability to strictly distinguish factual truth conditions from simple topic overlap.

Key Results

  • Superior Zero-Shot Accuracy: StateFactory achieved an average EPIC distance ($D_{EPIC}$, where lower is better) of 0.297 across the entire benchmark. This significantly outperformed zero-shot representation-free baselines like LLM-as-a-Judge (0.322) and the VLWM-critic (0.738), nearly matching the upper bound of a fully supervised model trained across all domains combined (0.282).
  • Enhanced Agent Planning: When integrated into a standard ReAct (Reasoning + Acting) planning agent to rank action candidates, StateFactory's dense reward signals yielded massive success rate improvements over the baseline:
  • AlfWorld: +21.64% (34.33% $\rightarrow$ 55.97%)
  • ScienceWorld: +12.40% (22.63% $\rightarrow$ 35.03%)
  • BlocksWorld: +8.00% (85.00% $\rightarrow$ 93.00%)
  • Breaking Deadlocks: Explicit reward signals successfully empowered agents to break out of logical "deadlocks" during long-horizon planning where pure text-based logic typically fails.

Limitations and Future Work

  • Computational Overhead: Running step-by-step state extraction and goal interpretation via large language models introduces notable inference latency and API costs, making real-time deployment challenging.
  • Embedding Dependency: The framework relies heavily on the quality of the text encoder. Weaker embedding models (like gemma-300m) cause a noticeable drop in alignment precision.
  • Future Directions: The authors suggest exploring more compact, specialized architectures to reduce inference overhead and continuously scaling the framework alongside advancements in LLM reasoning capabilities.

Summary updated

Abstract

Agents must infer action outcomes and select actions that maximize a reward signal indicating how close the goal is to being reached. Supervised learning of reward models could introduce biases inherent to training data, limiting generalization to novel goals and environments. In this paper, we investigate whether well-defined world state representations alone can enable accurate reward prediction across domains. To address this, we introduce StateFactory, a factorized representation method that transforms unstructured observations into a hierarchical object-attribute structure using language models. This structured representation allows rewards to be estimated naturally as the semantic similarity between the current state and the goal state under hierarchical constraint. Overall, the compact representation structure induced by StateFactory enables strong reward generalization capabilities. We evaluate on RewardPrediction, a new benchmark dataset spanning five diverse domains and comprising 2,454 unique action-observation trajectories with step-wise ground-truth rewards. Our method shows promising zero-shot results against both VLWM-critic and LLM-as-a-Judge reward models, achieving 60% and 8% lower EPIC distance, respectively. Furthermore, this superior reward quality successfully translates into improved agent planning performance, yielding success rate gains of +21.64% on AlfWorld and +12.40% on ScienceWorld over reactive system-1 policies and enhancing system-2 agent planning. Project Page: https://statefactory.github.io
BibTeX
@misc{shen2026reward,
  author = {Yijun Shen and Delong Chen and Xianming Hu and Jiaming Mi and Hongbo Zhao and Kai Zhang and Pascale Fung},
  title = {{Reward Prediction with Factorized World States}},
  year = {2026},
  eprint = {2603.09400},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2603.09400},
}
Figure