💬 NLP

HERO'S JOURNEY: Testing Complex Rule Induction with Text Games

The paper introduces HERO'S JOURNEY, a benchmark for evaluating rule induction in goal-directed text games, revealing that while state-of-the-art LLMs demonstrate some ability to infer hidden rules, their performance remains limited and uneven, particularly regarding procedural induction and multi-step execution.

Original authors: Anshun Asher Zheng, Kanishka Misra, David I. Beaver, Junyi Jessy Li

Published 2026-06-02

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Anshun Asher Zheng, Kanishka Misra, David I. Beaver, Junyi Jessy Li

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: A Video Game for AI Brains

Imagine you are playing a text-based adventure game (like an old-school Zork or a choose-your-own-adventure book). You are a warrior trying to save a captive. To win, you must defeat a guardian monster. But here's the catch: no one tells you which weapon defeats which monster.

The only clues you have are the "diaries" of other warriors who tried and failed (or succeeded) before you. You have to read their stories, figure out the hidden pattern (e.g., "Oh, dragons need fire swords, but goblins need water swords"), and then apply that rule to a new monster you've never seen before.

This paper introduces a new test suite called HERO'S JOURNEY. It's like a gym for Artificial Intelligence (AI) to test if it can actually learn rules from examples and then execute them correctly, rather than just guessing or memorizing answers.

The Two Main Challenges

The researchers found that current AI models (the "smart" computers) struggle with two specific things in this game:

1. The "Detective" Problem (Rule Induction)

The AI has to act like a detective. It looks at the clues (the other warriors' stories) and has to deduce the secret law of the universe.

The Analogy: Imagine you see three people entering a club.
- Person A (Wearing Red) gets a VIP pass.
- Person B (Wearing Blue) gets a regular pass.
- Person C (Wearing Red) gets a VIP pass.
- The Rule: "Red means VIP."
- The Test: If a new person (Person D) wearing Red shows up, does the AI know to give them a VIP pass?
- The Paper's Finding: The AI is okay at this simple detective work, but it often gets confused when the rules get complicated (like if "Red" means VIP unless the person is also wearing a hat).

2. The "Butler" Problem (Procedural Execution)

Knowing the rule is one thing; doing the steps to win is another. The AI isn't just asked "What weapon do you need?" It has to actually play the game: "Go to the shop," "Buy the sword," "Walk to the castle," "Fight the monster."

The Analogy: Imagine you know the recipe for a cake (the rule). But when you try to bake it, you forget to turn on the oven, or you mix the flour after you put the cake in the oven.
The Paper's Finding: This is where the AI really struggles. Even if the AI figures out the correct weapon, it often messes up the order of actions. It's like a brilliant chef who knows the recipe but keeps dropping the eggs on the floor.

The Eight Levels of Difficulty

The researchers built eight different "levels" in this game to test different types of thinking:

Simple Math (Additive): "The weapon size is the monster's height + its weight." (Easy addition).
Mix and Match (Compositional): "The weapon's size comes from the monster's height, and the color comes from its weight." (Two separate rules working at once).
The "If/Then" Switch (Conditional): "If the monster is a Dragon, its weight decides the color. If it's a Goblin, its weight decides the size." (The rules change depending on the situation).
The "Special Exception" (Override): "Usually, the monster's height decides the weapon. BUT, if the monster is a 'Chirurgeon' (a special role), it always needs a giant sword, no matter what." (One rule breaks all the others).

They tested both Attribute tasks (figuring out what item to use) and Procedural tasks (figuring out what order to do things in).

What Did They Discover?

1. Humans Win, AI Stumbles

When humans played this game, they were much better at both figuring out the rules and executing the steps.

The Gap: On average, humans were 13% better at finishing the game efficiently and 30% better at explaining the rule out loud.
The "Blind Spot": Some AI models could finish the game successfully, but when asked to explain how they did it, they couldn't. This suggests they might be "cheating" by guessing or copying patterns from the examples rather than truly understanding the logic.

2. The "Execution Bottleneck"

The paper found that the hardest part for AI isn't always thinking; it's doing.

The Metaphor: Imagine a GPS that knows the perfect route to your destination (the rule) but keeps telling you to turn left when you're already at the gas station (the execution error).
The AI often knows the answer but fails to perform the sequence of actions correctly in the game environment.

3. "Magic Words" Don't Help Much

The researchers tried tricking the AI by using real names (like "Dragon" and "Sword") versus nonsense words (like "Krev" and "Zorp").

The Result: It didn't matter much. The AI didn't get a boost from knowing what a "Dragon" usually needs. This proves the test is actually measuring logic, not just the AI's memory of movies or books.

4. Current "Fixes" Are Weak

The researchers tried using special "prompting tricks" (like telling the AI to "think step-by-step" or "check your work") to help it.

The Result: These tricks helped a little bit with the simple "what item to buy" tasks, but they did not help with the complex "how to do the steps" tasks. The gap between AI and human performance remains wide.

The Bottom Line

HERO'S JOURNEY is a new way to test if AI can truly learn from experience and act on that knowledge, rather than just memorizing answers.

The paper concludes that while AI is getting smarter at spotting patterns, it is still bad at applying those patterns in complex, multi-step real-world scenarios. It's like having a student who can solve a math problem on a test but can't figure out how to use that math to build a bridge. The researchers hope this game will help developers build AI that can actually do things, not just say things.

Technical Summary: HERO'S JOURNEY

Problem Statement

Current Large Language Model (LLM) agents face significant challenges in inductive reasoning, particularly when required to infer hidden rules from demonstrations and apply them to novel situations through multi-step execution. Existing benchmarks often fail to address three critical gaps:

Lack of Procedural Context: Induction is rarely tested within a goal-directed, multi-step execution setting where the inferred rule must drive a sequence of dependent actions.
Oversimplified Rule Interactions: Evaluations typically test atomic mappings in isolation rather than complex interactions between rules (e.g., conditional logic or overrides).
Identifiability Issues: Demonstrations often leave multiple rules consistent with the evidence, making it unclear whether a model has induced the specific target rule or merely found a coincidental pattern.

The paper posits that for agents to be truly capable of inductive reasoning, they must not only identify a pattern but also execute it correctly in a dynamic environment where errors force a restart.

Methodology: HERO'S JOURNEY

The authors introduce HERO'S JOURNEY, a benchmark suite for rule induction in goal-directed episodic tasks, instantiated as a deterministic text-based adventure game.

Task Structure

The framework consists of 8 tasks divided into two families, each with four structural rule forms:

Attribute Induction Tasks: The agent must infer a hidden mapping from entity attributes (e.g., class and role) to required item properties (e.g., weapon size and color).
- Additive: Attributes contribute independently to a scalar sum.
- Compositional: Attributes independently control separate output dimensions (e.g., one controls size, the other color).
- Conditional: One attribute determines a "regime" that dictates which dimension the second attribute controls.
- Override: A specific value of one attribute overrides the standard mapping for all values of the other attribute.
Procedural Induction Tasks: The agent must infer hidden steps or ordering constraints within a goal procedure (e.g., inserting a ritual or potion drink at a specific point in the sequence). These tasks mirror the four structural forms above but map attributes to process variants (action type, ordering, and count).

Design Principles

Procedural Execution: Agents must act in an environment (Go, Buy, Defeat, etc.) rather than simply outputting an answer. Success requires executing the correct sequence of actions.
Identifiability Conditions: The source demonstrations are curated to form a "connected bipartite graph" over attribute values. This ensures the target rule is the only consistent explanation for the data, preventing ambiguity.
Lexical Grounding: Tasks can be run with semantic names (e.g., "dragon," "sword") or nonce names (e.g., "krev_A," "vrel_Z") to disentangle structural induction from pre-trained world knowledge.

Evaluation Metrics

Performance is measured using two complementary metrics:

Rule Verbalization (RV): An LLM judge scores the model's ability to explicitly articulate the hidden rule on a 0–2 scale.
Efficiency-Calibrated Success Rate (ECSR): A behavioral metric defined as $SuccessRate \times NormEff$ $S u ccess R a t e \times N or m E f f$ .
- NormEff normalizes the number of attempts against a brute-force enumeration ceiling. A model that succeeds on the first try has a score of 1.0; one that exhausts all possibilities has 0.0. This distinguishes true rule induction from trial-and-error guessing.

Key Results

The authors evaluated state-of-the-art proprietary and open models (including GPT-5, Gemini, Qwen, and LLaMA variants) against human baselines.

Performance Gap: Humans consistently outperform all models, with a margin of 13% on ECSR and 30% on RV. While the strongest models approach human-level ECSR on select attribute tasks, they lag significantly on procedural tasks and rule verbalization.
Induction vs. Execution: There is a positive correlation between RV and ECSR, suggesting that models that can verbalize the rule also execute it more efficiently. However, this correlation is weaker for procedural tasks.
The Execution Bottleneck: A "format gap" analysis reveals that for many models, accuracy in a direct Question-Answering (QA) setting is significantly higher than in episodic execution. This indicates that multi-step execution adds a distinct bottleneck beyond rule identification.
Surface Semantics: Surface semantics (semantic vs. nonce names) have minimal effect on performance, suggesting models are not relying heavily on pre-trained world knowledge associations.
Steering Methods: Induction-specific steering methods (e.g., ReAct, IDEA, Hypothesis Refinement) show limited gains. They improve performance on attribute tasks but fail to provide reliable improvements on procedural tasks, indicating that the gap in procedural induction remains an open challenge.
Contextual Bias: In some conditional tasks, models succeed by copying seen examples from the context rather than inducing the rule, particularly when the demonstration set is small or underdetermined.

Significance and Claims

The paper claims that HERO'S JOURNEY represents a necessary step toward evaluating the inductive reasoning ability of AI agents in realistic, goal-directed settings.

Beyond Static Patterns: The benchmark demonstrates that the ability to identify a pattern does not guarantee the ability to act on it. The "execution bottleneck" reveals a critical weakness in current LLMs when translating abstract rules into concrete, multi-step plans.
Procedural Induction as a Frontier: The results suggest that while models show some capacity for attribute induction, procedural induction (inferring and executing complex action sequences) remains a significant unsolved problem.
Methodological Rigor: By enforcing identifiability conditions and distinguishing between rule articulation and behavioral efficiency, the framework provides a more principled way to assess whether a model has truly learned a rule or is merely exploiting statistical biases in the training data or context.

The authors conclude that while LLMs show evidence of rule induction, the capacity is limited and uneven. The gap between inducing a rule and executing it in a complex environment remains a primary hurdle for deploying autonomous agents in real-world scenarios where rules are unspecified and must be learned from experience.