Han et al.: Sorting Out When Learning Order Matters, by Computational Complexity — Fukai Reads

TL;DR

Everyone says the order of learning matters. The sequence of tutorials in a puzzle game, the unlock order of a skill tree, the arrangement of stages. But we have almost no way of measuring how much it matters before we start arguing about it. A new preprint from Han and colleagues at UC Davis takes the optimisation of learning order over prerequisite-linked concepts head-on as a computational problem, and delivers three answers. First, the stochastic nuisance of failed attempts and retries can be removed exactly, simply by dividing the cost by the success probability. Second, even so, finding the optimal order remains NP-hard. Third, before you start optimising you can cheaply compute an upper bound on how much reordering could possibly gain you.

The third is the one that bites in practice. The authors apply this diagnostic to real data from an introductory university computer science course — 294 students and 70,893 interactions — and confirm that less than 0.2% of the expected cost is available to sequencing at all. In fact even the plain linear syllabus order deviated from the optimum by only 0.034%. For this course, the fact that optimising the order is pointless can be established before optimising.

Curricula with the opposite structure do exist. In the public Junyi Academy corpus, 68 targets had search spaces exceeding ten million states. And on a synthetic family the authors call the sibling-transfer trap, a greedy order that picks by immediate success probability loses between 28.3% and 45.1%. Some layouts are order-sensitive and some are not, and you can tell which in advance — that is the spine of this paper. Note that this is arXiv:2608.05455, a preprint submitted on 5 August 2026, not yet peer reviewed and not yet widely discussed.

Introduction

The authors are Zonglin Han, Yichen Chen, Jiawen Jiang, Tongan Shi and Kristian A. Stevens. Han, Chen and Stevens are at the Department of Computer Science, University of California, Davis; Jiang is at the International Digital Economy College, Minjiang University; Shi is at the School of Computer Science and Artificial Intelligence, Liaoning Normal University. The paper is arXiv:2608.05455, classified under cs.AI and cs.DS, submitted on 5 August 2026, eleven pages with one figure and one table. It is a preprint, not a peer-reviewed publication, and is not yet widely discussed.

Let me say why I picked this paper today. If you make puzzles, you spend an unreasonable amount of time on level order. Should stage three and stage five be swapped? Does this mechanic get introduced before or after the compound level that stacks everything? And most of the time that argument never resolves. It never resolves because there is nothing to decide it with. This paper does not hand you the answer; it hands you an estimate of whether the argument is worth having. I found that appealing.

One more thing. The paper's subject is educational curricula, but its vocabulary — a directed acyclic graph of prerequisites, a set of mastered concepts, a set of moves currently available — is exactly the vocabulary of skill trees and stage progression. It translates cleanly into game design. The authors name their planning problem Ariadne, after the thread lowered into the labyrinth.

Background

First, the setting. In educational technology, deciding what to present to a learner and in what order is called instructional sequencing. Most prior work stands on the generating side: how to construct a sequence. Multi-armed bandits (a framework for finding the good option by trying several), reinforcement learning (learning by trial and error which actions lead to higher reward), partially observable Markov decision processes (POMDPs, sequential planning when the learner's internal state is not directly visible), prerequisite-aware Markov decision processes, and more recently large language models.

The authors argue that four questions logically precede all of that. Do stochastic learning dynamics genuinely require stochastic planning? When does dependence on the learner's state create value in sequencing at all? Which transfer structures — transfer meaning that learning one concept changes how easy another becomes — induce ordering conflicts? And what governs the difficulty of exact search? The paper declares up front that it answers all four.

The state space itself has a long history. Knowledge space theory in mathematical psychology represents a learner as the subset of items mastered. Once a prerequisite partial order is imposed, states form a lattice of order ideals — sets that, whenever they contain an element, also contain all of its prerequisites. The authors are explicit that their contribution is not the state space but the planning problem on it: finding the order that minimises expected cost, and characterising how hard that is.

Approach

The model is startlingly plain. A curriculum is a directed acyclic graph of prerequisites. A learner state is the set of mastered concepts, closed under prerequisites. At a given state the available moves are exactly the unmastered concepts whose prerequisites are all satisfied. The authors describe this as a graph-theoretic reading of Vygotsky's zone of proximal development — the band that is out of reach alone but reachable with support. One attempt incurs a fixed cost and succeeds with some probability. A failed attempt leaves the state unchanged.

From this comes the first result. If failure leaves the state unchanged and success probabilities do not vary with time, the stochasticity can be removed exactly. The expected number of attempts until success is the reciprocal of the success probability, so you can replace each move by a deterministic cost equal to the per-attempt cost divided by that probability. According to the authors, the original stochastic problem and the rewritten deterministic shortest-path problem share identical optimal values and identical sets of optimal moves. There is an implementation consequence too: heavy machinery for handling solutions with loops, such as LAO*, has nothing left to do here.

Second, the authors supply a tool for bounding the value of reordering. For a single concept, look across every state in which it is legally attemptable and take the difference between the largest and smallest rewritten cost. Sum that difference over all concepts, and no two valid orders can differ in total cost by more than that sum. Better still, if success probabilities are monotone — never decreasing as more is mastered — the per-concept difference is obtained exactly with just two oracle queries. You get an upper bound on the headroom of sequencing without expanding a single lattice state.

Third, when you do want the exact optimum, the solver is A* (a search algorithm that uses an estimate of the remaining cost to goal to expand promising directions first). The estimate is the sum, over remaining concepts, of the cost each would have under its most favourable conditions. Because that estimate never exceeds the true cost, A* returns an exactly optimal answer. The state lattice is never built explicitly; states are generated on demand.

Findings

The complexity map is the spine of the paper. After the stochasticity is removed, the ordering problem is NP-complete. Moreover, according to the authors, it stays NP-hard even under severe restrictions: no prerequisite edges at all, uniform attempt costs, transfer strengths that are only zero or one, success probabilities monotone in the state, and every success probability at least one half. The reduction is from minimum feedback arc set in tournaments (lining up a round-robin results table so as to minimise the number of upsets). Hardness comes not from respecting prerequisites but from the ordering conflicts induced by state-dependent transfer.

The hardness is not uniform, though. If you merge the transfer preferences (doing u first makes v easier) with the hard prerequisites into one graph and that graph has no cycles, then any topological ordering — any arrangement that never runs against an arrow — is globally optimal and can be constructed in linear time. If the width of the prerequisite partial order — the maximum number of strands that can be advanced in parallel — is fixed, exact dynamic programming runs in polynomial time. And when transfer acts affinely, there is a fixed-parameter tractable algorithm in the number of edges that must be cut to break the cycles.

To the experiments. From ECS32A, an introductory computer science course at UC Davis, 70,893 interactions from 294 students were mapped onto a 61-concept prerequisite graph and evaluated over ten target closures. The diagnostic reports that less than 0.2% of the expected cost is available to sequencing. In Table 1, even the worst condition — the plain linear syllabus order — has a normalised regret of 3.385 x 10^-4, that is 0.034%. Picking randomly among available moves gives 2.633 x 10^-4. The authors call this a doubly easy regime: little value in optimising, and little space to search.

A contrasting curriculum is shown too. The public Junyi Academy corpus has 835 exercises; its sink-target closures have median width eight and maximum width eighteen, a median of 96,608 reachable states, and 68 closures exceed the ten-million-state enumeration guard. On the authors' constructed sibling-transfer trap — an antichain of siblings that individually look easy but chain their transfer when taken in the right order — greedy sequencing incurred regret between 28.3% and 45.1%. On that family, dynamic programming expands a number of states that grows exponentially in the width while A* expands only on the order of the width itself. Where order genuinely matters, search matters too.

How to use this

One: reordering levels in a Sokoban-like. Draw a prerequisite graph over mechanics, and from your play data compute, for each mechanic, the first-attempt clear rate among players who already understand its predecessors versus those who do not. The ratio of those two is the per-concept swing the paper talks about. The paper also gives a multiplicative bound: no valid order can be worse than the optimum by more than the largest such ratio. If that ratio is near one for every mechanic, close the reordering debate. I would build the dashboard that computes this ratio before building any reordering tool.

Two: procedural level selection in a hypercasual game. When the generator picks the next level by immediate clear rate alone, it can lose in exactly the shape of the sibling-transfer trap: serving the sibling that looks easiest first forfeits the transfer that would have helped the ones after it. The remedy is not exotic. If transfer can be approximated affinely, an exact solution is tractable in the number of edges you would have to cut to break the cycles. If it is too tangled for that, that is itself a signal that the design is over-coupled.

Three: branching tutorial design. The width of the prerequisite order governs search cost, and that number carries straight into design. In the paper's data, width four means at most 47 reachable states and instant exhaustive enumeration; width eighteen means over ten million. The desire to let players progress freely and the desire to verify that progression is optimal trade off against each other along that single number. It reads as worth carrying width as an explicit design budget.

Four: the ordering within one session of a daily puzzle. The framework assumes mastery is never forgotten, which does not hold across days. But that also means it applies cleanly where forgetting does not bite: the sequence of stages inside one session, or a single tutorial week. Check it with a prerequisite graph and one diagnostic number, and if ordering has no headroom, spend that time elsewhere. There is value in being able to justify the decision not to optimise the order.

Limitations

Start with what the authors themselves concede. The largest issue is that the evaluation is closed-loop: in the ECS32A experiments, the learner model used for planning and the evaluator used for scoring are the same object. So the zero regret of the exact Ariadne planner is a protocol identity, not an empirical result, and the authors say so explicitly. That model is only moderately predictive on held-out sessions — AUC 0.775 with all features, 0.611 with history ablated. The conclusions concern the planning landscape induced by that frozen model, not real learner counterfactuals, as the authors repeat.

Further. The Junyi Academy analysis is topology evidence, not planner evaluation. The first-attempt proxy (median 5.6%, maximum 12.5%) cannot rule out that students who already mastered prerequisites are systematically stronger, which would inflate apparent state dependence; the authors call it an exploratory diagnostic rather than a certified bound. And the collapse result fails when failures update beliefs, when costs depend on attempt history, when mastery can be forgotten, when actions have more than two outcomes, or when the objective is risk-sensitive. The paper also reports a reversal: in the BKT and DKT conditions, exact solutions beat greedy ones under their own objective yet scored worse under the shared evaluator. Exact optimisation amplified the learner model's error.

What Fukai would add here is two further points. First, the diagnostic is an upper bound on the gain from reordering, not a lower bound. The 0.2% figure means you cannot gain more than that; it does not mean order design is meaningless. Whatever the model leaves out of its objective — boredom, surprise, giving up — was never being measured. Second, the objective itself, minimising expected total cost, is a poor fit for games. A tutorial with the learning cost squeezed all the way out is usually dull. This paper is about shortest paths, not good paths. In education those two are close; in play they are not necessarily close at all.

Fukai's reading

I want to place this work in the lineage of putting a budget on design arguments — and this section alone is my own interpretation. In practice, debates about order, difficulty and timing of introduction consume time without ever resolving. What this paper offers is not the answer about order but an estimate of how much the argument is worth having, and that estimate arrives before any optimisation, at two oracle queries per concept. In the vocabulary of design criticism, this is close to automating the deliberation about whether deliberation is warranted. One other thing caught me: when the learner model was only moderately accurate, exact optimisation made results worse rather than better. The authors close with the line that planning is a lever and the learner model is its fulcrum. If the fulcrum is loose, do not lengthen the lever. I have seen implementations that polish level-selection optimisation while the underlying player model remains dubious, and I recognise the shape.

Closing

For those who want to go further, here is a map of the surrounding terrain. Published at almost the same time, Pasechnyuk-Vilensky's Order-sensitive sequential interventions on ideal lattices (arXiv:2604.26472) characterises order sensitivity on the same ideal lattice through a local measure. According to the authors of this paper, neither that local bound nor their global one uniformly dominates the other. Read side by side, the two show that there are at least two distinct ways to measure the property of order not mattering.

If you want the background lineage, look at knowledge tracing — the technique of estimating which concepts a learner has mastered — from Corbett and Anderson's Bayesian Knowledge Tracing (1995) through Piech and colleagues' Deep Knowledge Tracing (2015). It clarifies why this paper keeps insisting that it does not touch the learner model itself. Coming from the games side, Narvekar and colleagues' survey of curriculum learning for reinforcement learning (2020) handles the same problem in a different vocabulary. The ordering problem shows up in the same shape from education, machine learning and game design alike.

Sources

Papers and related material referenced in this article:

・Stochasticity Is Not the Hard Part: Reduction and Complexity in Instructional Sequencing over Prerequisite DAGs (Zonglin Han, Yichen Chen, Jiawen Jiang, Tongan Shi, Kristian A. Stevens, 2026, arXiv preprint)

・DOI: 10.48550/arXiv.2608.05455

・Related: Order-sensitive sequential interventions on ideal lattices (Pasechnyuk-Vilensky, 2026, arXiv preprint)

・Related: Deep Knowledge Tracing (Piech et al., 2015, NeurIPS)

・Related: Curriculum Learning for Reinforcement Learning Domains: A Framework and Survey (Narvekar et al., 2020, JMLR)