Invented-Rule Story Worlds for Verifiable Long-Range Coherence

Language models write and read long stories fluently, but they lose track of what is true. A character who lost a key in chapter two opens the locked door in chapter nine, and nobody notices. Measuring this failure is hard for two reasons. The long stories we test on are mostly scraped from the web and have probably been seen in pretraining. And "is this story coherent?" usually has no checkable answer. We propose to borrow a tool from game design that addresses both problems. Procedural content generation means building game content with algorithms instead of by hand. Within that field, rule generation invents a game's mechanics themselves. Our idea is to generate each story's world rules fresh, run a simulator under those rules to produce a long event history, and then have a language model write that history as prose. Because the simulator knows the true state of the world at every point, every coherence question has an exact answer. Because the rules are new for each instance, a model cannot answer from memorized text or from everyday commonsense. It has to track what the story actually said.

The same generator serves two purposes. It is a contamination-proof benchmark in which we control the token distance between a cause and the event it constrains. It is also a source of checkable rewards for reinforcement learning, so we can ask whether training on invented-rule worlds teaches a model to track narrative state from the text in a way that transfers to real long-context tasks. Our central bet is narrow and falsifiable. Training on worlds whose rules contradict commonsense should transfer better than training on worlds whose rules match it. The reason is that only invented rules force the model to rely on what the text says rather than on what it already believes.

Core Claim

Existing programmatic story generators fix the world's physics in advance and keep it intuitive. Two things become possible once the rules themselves are generated per instance and the events are spread over tens of thousands of tokens. First, we can measure how much of a model's apparent narrative tracking is really retrieval of commonsense or memorized priors. We do this by comparing performance on an intuitive-rule world with performance on an otherwise identical world whose rules have been swapped. This is a narrative analogue of the symbol-remapping test in A²RBench, where frontier models lost 17.7% accuracy when digits were replaced by letters. Second, we obtain a reward for detecting contradictions and predicting consequences over long spans, with exact answers. Prior long-context training methods lack such a reward. Our hypothesis is that reinforcement learning on invented-rule worlds improves contradiction resolution on the BEAM benchmark more than equal-compute training on intuitive-rule worlds or on reordering human documents.

Where This Sits

Three lines of prior work motivate the gap. DyVal builds reasoning problems on the fly from random dependency graphs. It showed that models with strong static-benchmark scores, such as phi-1.5 and WizardMath-13B, "scored nearly zero" on fresh instances, and that depth hurts much more than breadth. Its tasks, however, are arithmetic, logic and graph search, not prose. A²RBench generates abstract grid and sequence tasks and keeps only those that pass a round-trip check: a forward program and its inverse must recover the input. We reuse that round-trip idea to verify our prose rendering, but our domain is extended narrative, not array transformations. Beyond a Million Tokens built BEAM, 100 conversations of up to 10M tokens, and found that contradiction resolution is the weakest skill across all models. Its narratives come from unverified LLM expansion of seeds, so its gold answers rest on the generator not having slipped. Our proposal keeps BEAM as a transfer target and replaces unverified expansion with a simulator.

The closest work, and the one we must clearly beat, is Explore Theory of Mind (data released as facebook/ExploreToM). It writes stories in a small hand-built action language with formal state updates and uses A* search to find story structures that defeat models. Fine-tuning Llama-3.1-8B on its 79,700 examples gave +27 points on ToMi and +29 on Hi-ToM. It differs from our proposal in three ways. Its stories are a few actions long. Its action semantics are fixed and intuitive (moving objects, peeking). Its target is belief tracking, not global consistency. We extend the state-tracking idea to long horizons and, more importantly, make the rules a generated variable rather than a constant.

On the training side, Document Reconstruction Unlocks Scalable Long-Context RLVR masks paragraphs of books, papers and code and rewards a model for restoring their order. For Qwen2.5-7B this gives a roughly 10-point RULER gain at 30,000 samples, and 14k reconstruction samples beat SFT on 46k curated QA pairs. It is our strongest competitor. Its signal tests ordering rather than consistency, and its documents are human-written and likely seen in pretraining. Rubrics as Rewards extends reinforcement learning to open-ended answers with LLM-judged checklists, and also documents that holistic judge scores invite reward hacking. That finding is why we insist on simulator-checked rewards. CPL shows that training abstract plans on math transfers to code (+12.2% HumanEval) and science (+8.6% GPQA). A²RBench's remapping drop suggests such transfer may ride on shared surface tokens. This is the tension our rule-swap ablation is designed to probe in the narrative setting.

The PCG methods we reuse come from game design. General video game rule generation generates interaction and termination rules for fixed level layouts using random, constructive and feasible–infeasible two-population search (FI-2Pop, an evolutionary method that keeps rule-violating candidates in a separate population and repairs them). Mario Level Generation From Mechanics Using Scene Stitching uses FI-2Pop to stitch scenes to a target action sequence, reaching 87–100% playability. We apply the same machinery to text: rules are generated, and event sequences are searched to hit a target pattern of long-range dependencies.

Research Program

The generator has four stages. First, a rule sampler draws a small world specification: entity types, a handful of properties, and roughly ten to thirty transition rules written in a VGDL-like action language. A rule might read "a lantern carried across water goes out and cannot be relit by the same character". Each specification comes in two versions with identical logical structure. The intuitive version uses familiar mechanics. The invented version uses mechanics drawn so that at least half contradict a commonsense default; for example, "fire is extinguished by dry wood". The two versions share graph structure, event count and dependency distances, so any accuracy gap between them isolates reliance on priors.

Second, an event planner searches over action sequences under the rules. Its objective rewards placing causally linked pairs (a setup event that constrains a later event) at chosen distances. FI-2Pop keeps the history legal, as in the Mario work, and lets us set dependency distance and chain depth as independent difficulty knobs, following DyVal's lesson that depth matters most.

Third, a language model renders each event's state change as a paragraph. Taking the round-trip idea from A²RBench, a separate extractor reads each paragraph back into a state change. We keep the paragraph only if the extracted change matches the simulator's change exactly; otherwise it is regenerated. The rules are stated once near the beginning, the way a fantasy novel establishes its magic system, and are never repeated.

Fourth, questions are produced automatically. Contradiction-detection items insert one paragraph that violates the rules or the current state at a known position, and the model must find it and name the earlier fact it conflicts with. Consequence items ask what must be true after a given event. State items ask about an entity's property at a given point. Every answer is computed by the simulator. We target story lengths from 8k to 64k tokens. The upper end matches Document Reconstruction's training range, and the lower end leaves room for many episodes per GPU-hour.

Baselines

The do-nothing reference is the base model, Qwen2.5-7B-Instruct, chosen to match Document Reconstruction's reported setting, evaluated zero-shot with chain-of-thought on every benchmark. All trained variants start from this checkpoint.

The strongest existing method is Document Reconstruction RLVR from Document Reconstruction Unlocks Scalable Long-Context RLVR. We will rerun its recipe ourselves: GRPO (group relative policy optimization, a reinforcement learning method that scores each sampled answer against others for the same prompt) with the same maximum context, the same number of training samples and the same GPU-hours as our method, and the same learning-rate sweep size. Its reported figure is a ~10-point RULER average gain for Qwen2.5-7B at 30,000 samples. For LongBench v2 the file reports only "moderate, consistent improvements", so no reported result was found on Lacuna for a LongBench v2 number. Beating it means matching its RULER gain within noise while exceeding it on BEAM contradiction resolution and event ordering, which are the abilities our reward targets. If we only match it everywhere, the simpler method wins.

The second strong baseline is a length-extended ExploreToM. We generate ExploreToM-style stories with its fixed action semantics, chain them to the same lengths as ours, and train with the same reward and budget. This tests whether any long, verified, simulated narrative suffices. Its reported result is +27 on ToMi and +29 on Hi-ToM for fine-tuned Llama-3.1-8B in Explore Theory of Mind. We report ToMi and Hi-ToM for every variant so we can see whether our data gives up that gain.

The key ablation trains on the intuitive-rule twins of our own worlds, identical in every respect except rule content. If invented rules do not beat intuitive rules on transfer, the core claim fails.

A judge-reward baseline trains with a rubric-scored LLM judge in the style of Rubrics as Rewards, on the same invented-rule stories but without simulator answers. It isolates the value of exact verification over judged coherence.

For the memory side of BEAM, we report the LIGHT memory scaffold from Beyond a Million Tokens as an inference-time comparison. LIGHT reported 3.5%–12.69% average improvement over the strongest baselines. The file gives no per-category contradiction-resolution number, so no reported result was found on Lacuna for that category. We also test whether our training adds to LIGHT rather than substituting for it.

Why not just…?

Why not just run Document Reconstruction on post-cutoff documents? Fresh documents fix contamination but not the reward. Restoring paragraph order can be solved from local discourse cues (topic shifts, transition words) without ever checking whether a later fact contradicts an earlier one. This alternative is a real threat on RULER-style retrieval, and we expect it to tie us there. The experiment that settles it is the BEAM contradiction-resolution comparison at equal compute, plus a check on our own held-out contradiction items. If reconstruction matches us on both, we will report that the simulator buys nothing beyond freshness.

Why not just make ExploreToM stories longer? This is the closest alternative, and the length-extended ExploreToM baseline exists to answer it directly. Our reason to expect a gap is that fixed, intuitive action semantics let a model fill state gaps from priors rather than from the text, which is the shortcut A²RBench's remapping result exposes in symbolic tasks. If the length-extended ExploreToM baseline matches our invented-rule training on transfer, the contribution narrows to a benchmark rather than a training method, and we will say so.

Why not just have an LLM judge score story coherence? Rubrics as Rewards itself reports that holistic judge scores invite reward hacking toward confident, verbose answers. ExploreToM showed that frontier models collapse (0% for Llama-3.1-70B, 9% for GPT-4o on some action sets) exactly where formal state tracking is needed, which makes such models unreliable judges of long-range consistency. The judge-reward baseline measures this directly on identical stories.

Why not just paraphrase or token-swap existing long-story benchmarks? Surface rewriting leaves the underlying events and their real-world logic intact, so a model that knows the plot or the commonsense can still answer. DyVal's near-zero scores for statically strong models show that structural novelty, not surface novelty, is what exposes the gap. Our rule-swap twin pairs are a controlled version of this idea that changes structure-relevant content while holding difficulty fixed.

Proposed Experiments and Decisive Checks

The benchmark study evaluates base and frontier-accessible open models on 2,000 generated items per condition. Conditions cross intuitive versus invented rules, four dependency distances (1k, 4k, 16k and 48k tokens) and three chain depths. The first decisive check is the shape of the invented-minus-intuitive gap as distance grows. If the gap widens with distance, models increasingly substitute priors for text as context lengthens, a contamination-like effect at the level of world knowledge that static benchmarks cannot see. If the gap is flat and near zero, the rule manipulation is not doing work and the training claims become moot.

We also audit the generator. We report the round-trip rejection rate of the renderer. Human annotators check 200 accepted stories for rendering errors, and we target under 2% rule-inconsistent paragraphs. We also check that difficulty does not fall at large world sizes. A²RBench saw such a drop, its "V-shaped" curve where the author model simplified 3D rules, and we guard against the same failure in our rule sampler.

The training study runs GRPO on 30,000 generated episodes for each data condition at matched compute. We evaluate on BEAM (contradiction resolution and event ordering categories), RULER, LongBench v2, ToMi and Hi-ToM, plus held-out invented-rule worlds whose rule templates never appeared in training. The second decisive check is the key ablation: invented-rule training must beat intuitive-rule training on BEAM contradiction resolution by more than seed variance across three seeds. The third is the head-to-head with Document Reconstruction on the same metric at equal compute.

Finally, as a generation-side probe, we use each trained model as the drafting model in a Re3-style plan-and-draft loop, following Re3, which reported a 14% absolute gain in stories judged to have a coherent plot. Instead of WritingPrompts premises, which are probably contaminated, we give it fresh invented-rule worlds as premises. The engine then counts rule and state violations in the generated text directly. This tests whether better reading-side tracking turns into fewer contradictions when the model writes.