Language models can write thousands of fluent words, but over long stretches they lose the thread. Characters change, clues contradict each other, and plot points drift away from the premise. Systems that plan first and then write, which draft an outline and realize it section by section, reduce this drift. Nobody can measure how much, though, because the only judges are humans or holistic model ratings, and neither checks whether the finished text actually carries out the plan. We propose to turn a reading-comprehension benchmark inside out. MuSR builds murder mysteries and object-tracking stories from symbolic reasoning trees and asks models to solve them. We instead give a model the tree and ask it to write the story. The story is then scored automatically by whether independent reader models can solve it, whether they can solve it too early, and whether it breaks when its events are shuffled.
The plan is a known symbolic object, so this setup separates two failures that current narrative work lumps together: making a bad plan, and failing to carry out a good one. That lets us test whether a result from code generation also holds for stories. In code, a model's self-written plan often hurts, while an expert plan helps a great deal (Beyond Code). The same scoring signals also work as step-level critics during generation. We use them to build a closed-loop writer that checks each chapter against the plan and repairs it. We expect this writer to extend coherent story generation past the depth-2 trees that MuSR's own pipeline could not exceed.
Core Claim
Our claim is that plan fidelity in long narrative can be measured without human raters, using probes derived from the plan itself. A reasoning tree is a structured list of facts, deductions, and a conclusion. From it we can ask three concrete questions of a generated story. First, is it recoverable: can a pool of reader models reach the right answer from the story nearly as well as from the bare fact list? Second, is it non-leaking: do readers stay near chance on prefixes that end before the designated reveal? Third, is it order-dependent: does shuffling the story's paragraphs hurt readers on tasks where time order matters? With these measures we expect to show two things. Self-generated narrative plans degrade faster with depth than oracle plans do. Probe-driven chapter repair closes much of that gap, where generic "critique and revise" prompting does not.
We write recoverability as $R = a_{\text{story}} / a_{\text{facts}}$. Here $a_{\text{story}}$ is reader accuracy given the generated story, and $a_{\text{facts}}$ is reader accuracy given the tree's leaf facts as a plain list. Dividing by the fact-list ceiling removes reader weakness from the score. This matters because GPT-4 reaches only 60.9% on MuSR Object Placement versus 95.0% for humans, so a raw accuracy would mostly measure the reader. Leakage is $L = a_{\text{prefix}} - a_{\text{chance}}$, measured on the prefix before the reveal chapter. Order sensitivity is $S = a_{\text{story}} - a_{\text{shuffled}}$.
Where the Directions Meet
Each input direction plays a different role. Hierarchical narrative planning supplies the systems under test. Re3 writes an outline, drafts each passage from a distilled summary plus one outline point, reranks candidates, and edits against a dictionary of character attributes. Agents' Room has separate planning agents write conflict, character, setting, and plot to a shared scratchpad, after which writing agents realize the story. Both assume the self-generated outline is a trustworthy anchor. Neither checks anything deeper than character attributes, so a causal or temporal contradiction can pass straight through.
Global narrative coherence supplies the failure modes we must keep in view. SNaC gives a span-level taxonomy of coherence errors: unintroduced characters, dangling references, jarring scene shifts, and contradictions. It also shows that ROUGE can be matched by a bare list of entity names. We use its taxonomy for human audits, so that high fidelity cannot be bought by writing a list of clues. BEAM finds that resolving contradictions is the weakest long-context skill even with million-token windows. That motivates probing contradictions explicitly rather than trusting longer context.
LLM reasoning limitations supply the hypotheses. The first comes from Beyond Code's finding on self-planning in code, described above. The second comes from Can Large Language Models Always Solve Easy Problems if They Can Solve Harder Ones?, which finds that models solve hard problems yet fail easier sub-problems. That suggests a consistency test: a writer that realizes a depth-3 tree should also realize each of its depth-2 subtrees. Two further papers supply method. Divide-and-conquer prompting shows that isolated sub-task contexts limit error build-up, but only when the sub-tasks are nearly independent. HVR shows that a symbolic validator which feeds violated preconditions back to the planner raises plan correctness on robot tasks from 17.72% to 94.19%, but it needs hand-written domain rules. Our probes are the narrative analogue of that validator. They come directly from the tree, so no domain rules need to be written by hand.
The GLUE line of work plays the role of an evaluation lens and a warning. GLUE's contribution was one scoring interface shared across heterogeneous tasks. We adopt that design across three domains: mystery, object tracking, and team allocation. Out of Order shows that GLUE classifiers keep 75–90% of their correct predictions when words are shuffled. That is the reason we do not rely only on entailment classifiers trained on GLUE's inference data to check whether a fact appears in the story. It is also the reason we add the shuffle test $S$ as a guard against bag-of-facts solutions.
Research Program
Task construction. We build the generative task, which we call Reverse-MuSR. For Object Placement, trees are sampled symbolically: a sequence of object moves, who witnessed each move, and a question about one character's belief. Ground truth can be computed exactly at any depth, which sidesteps MuSR's inability to build valid trees past depth 2 with GPT-4. A domain-specific story generator similar to ExploreToM could supply extra structures. For Murder Mystery and Team Allocation, we reuse MuSR's tree-completion pipeline and its validators at depth 2. We push to depth 3 only for trees that pass those validators.
Scoring harness. Each tree comes with a reveal index, which marks the chapter by which the answer should become deducible. It also comes with per-leaf questions, such as "where did Ana last see the key?", that probe whether each fact made it into the text. Readers are a fixed, held-out pool of models from different families than the writer, which prevents a writer from optimizing for its own reading habits. On a sample, we compute reader-pool accuracy on MuSR's human-validated stories. This calibrates the harness against text known to be solvable.
Systems under test. We vary three factors. The plan source is the oracle tree, a tree the writer generates itself from the same premise and answer, or no plan. The realization strategy is a flat single pass, Re3-style chaptering with rolling summaries, or isolated chapters in the divide-and-conquer style that receive only a structured state record. The repair mechanism is none, generic self-critique, or our probe-driven repair. Probe-driven repair runs the leaf, leakage, and contradiction probes after each chapter. If a probe fails, the writer receives the specific failure, for example "fact 4 is not recoverable" or "readers can already name the culprit at chapter 2", and must rewrite that chapter. In a secondary sweep, the probes also run every $k$ chapters, and a failure can trigger an update to later outline points. This tests in narrative the finding of When to Re-Plan: re-planning at every step hurt performance (LM loss 1.674 versus 1.640 with no plan), and a moderate commitment horizon was best (1.544 at $P=3$).
Baselines
The naive reference point is flat generation. The writer receives the premise and the answer and is asked to write a solvable story, with no tree and no repair. This is the floor that any planning method must clear.
The strongest existing method is MuSR's own chaptered story generator applied to the same trees. It is the only published system in the file that turns a reasoning tree into narrative. It already guarantees every leaf is mentioned by conditioning each chapter on one sub-branch, so it is the natural target to beat on recoverability. We run it with the same writer model and the same trees. Our comparison is on depth-3 trees and on leakage, neither of which its keyword validators check. No reported result found on Lacuna for automatic solvability or leakage scores of MuSR-generated stories. The only reported numbers are reader accuracies on the frozen benchmark: 80.4% for GPT-4 on Murder Mystery and 60.9% on Object Placement, against human scores of 94.1% and 95.0%. We treat these as the harness calibration point. To beat MuSR's generator, a system must match its $R$ at depth 2 and exceed it at depth 3 with lower $L$.
Re3 is the strongest hierarchical narrative writer. It is reported to give a 14% absolute gain in stories judged to have a coherent overarching plot on WritingPrompts. We reimplement its plan, draft, rewrite, and edit stages with the same writer model. We run it in two variants: one plans its own outline, and one receives the oracle tree as its outline. Agents' Room is run the same way, with the tree as the plot artifact on its scratchpad.
Generic self-refine is the obvious competitor to our repair loop. After each chapter, an LLM judge critiques coherence and the writer revises. It receives exactly the same number of critic calls and revision tokens as probe-driven repair.
The key ablation keeps the loop but replaces the probe feedback with a message saying only that a failure occurred. This isolates whether the benefit comes from specific, plan-derived feedback or merely from extra revision passes. All systems share the same writer model, trees, total generation-token budget, and three prompt variants tuned on a dev split.
Why not just…?
Why not just use an LLM judge to rate coherence? A holistic judge cannot tell whether a clue is missing, stated too early, or contradicted. SNaC's human agreement was only 0.19 on holistic scales and rose to 0.69 on specific error categories, so holistic judgments are noisy even for people. Agents' Room does report that an LLM judge correlates with humans at $\rho=0.85$, but for creativity, not plan fidelity. We will report judge scores alongside $R$ and $L$ and test on a human-audited subset which of them tracks SNaC error counts and human solvability. If the judge tracks these as well as our probes, that is a real finding against our harness.
Why not just add generic critique-and-revise to Re3? This is the real threat to the repair claim, and the matched-budget self-refine baseline and the uninformative-feedback ablation exist to settle it. The prior evidence favours specific feedback. HVR's jump in plan correctness came from naming the violated precondition, not from asking the model to check its work. Still, if self-refine matches probe repair on $R$ and $L$, we will report that the value lies in the measurement rather than in the loop.
Why not just give the model a long context and chain-of-thought and write in one pass? BEAM finds that long-context models degrade on contradiction resolution even at a million tokens. Chain-of-thought on MuSR still leaves large gaps to humans. The flat-generation baseline, which we also run with explicit step-by-step prompting, measures this directly at each tree depth.
Proposed Experiments
The first decisive check validates the harness itself. On a sample of generated stories, humans try to solve each story and annotate it with SNaC categories. $R$ and $L$ must predict human solvability better than an LLM judge's scores do. If they do not, the benchmark claim fails.
The second check is the self-planning curve. We plot $R$ against tree depth for oracle-plan versus self-plan writers. The Beyond Code hypothesis predicts that the gap widens with depth and that self-planned stories fall below flat generation at the deepest level.
The third check tests the repair loop. Probe-driven repair should raise $R$ and lower $L$ at depth 3 over both MuSR's generator and matched self-refine, without increasing SNaC contradiction or dangling-reference rates. We also check hard-to-easy consistency: how often a writer succeeds on a tree but fails on one of its subtrees.
The fourth check is order sensitivity on Object Placement. Stories that score well on $R$ but show near-zero $S$ are bag-of-clue lists, not narratives. We count them as failures, which is the GLUE shuffle lesson applied to generation.
Finally, the re-checking sweep over $k$ tells us whether narrative plans, like latent plans, are hurt more by revising too often than by committing too long.
References
- MuSR: Testing the Limits of Chain-of-thought with Multistep Soft Reasoning
- Beyond Code: Evaluate Thought Steps for Complex Code Generation
- Re3: Generating Longer Stories With Recursive Reprompting and Revision
- Agents' Room: Narrative Generation through Multi-step Collaboration
- SNaC: Coherence Error Detection for Narrative Summarization
- Beyond a Million Tokens: Benchmarking and Enhancing Long-Term Memory in LLMs
- Can Large Language Models Always Solve Easy Problems if They Can Solve Harder Ones?
- When Splitting Makes Stronger: A Theoretical and Empirical Analysis of Divide-and-Conquer Prompting in LLMs
- Hierarchical Planning for Complex Tasks with Knowledge Graph-RAG and Symbolic Verification
- Out of Order: How important is the sequential order of words in a sentence in Natural Language Understanding tasks?
- When to Re-Plan: Subgoal Persistence in Hierarchical Latent Reasoning