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:
- 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).
- 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:
- 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
Mugwith attributes likelocation: on the tableandfilled: empty). - 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.
- 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).
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.
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