Higher-Order Modeling for Non-Markovian Sequential Data

This direction is split into other directions: first-order Markov assumption. Its last version stays readable and citable here.

Version 1 of 141 papers45 conceptsfrozen 2026-10-04

Most algorithms that power our digital lives—from PageRank to basic recommendation engines—rely on a convenient lie: the Markov assumption. This principle suggests that to predict a user's next move, you only need to know their current state. In this "memoryless" view, your next click on a website or your next stop in a city is independent of the path you took to get there.

However, a growing body of research demonstrates that human behavior is rarely memoryless. Whether navigating Wikipedia, shopping for groceries, or traveling through a city, our future actions are deeply constrained by our historical context.

The Failure of the Memoryless Assumption

The first-order Markov model is computationally elegant but often biologically and behaviorally inaccurate. Michael K. Ng and Joshua Zhexue Huang argue that ignoring the historical context of a session oversimplifies user behavior, failing to represent complex, multi-step intents.

This isn't just a theoretical concern; it has practical consequences for system design. Peter Tselios and George Vouros found that modeling navigation as memoryless fails to capture how accumulated context shapes decision-making in complex information architectures. If a designer assumes a user is "starting fresh" on every page, they may fail to provide the links or information the user actually needs to complete a multi-step task.

Quantifying Human Memory

If the Markov assumption is a lie, how much "memory" do humans actually have? Philipp Singer and Denis Helić investigated this by analyzing topical transitions in web browsing. They discovered that while individual page-to-page transitions might appear Markovian, humans actually possess a "topical memory" of 2 to 3 steps.

In their work on Memory and Structure in Human Navigation Patterns, they show that our intent creates a "path dependency." For example, a user who reached a "Biology" page from a "Chemistry" search has a different intent—and thus a different probability of their next click—than a user who reached that same "Biology" page from a "Medical School Admissions" portal.

The Curse of State-Space Explosion

The obvious solution to the memory problem is to use Higher-Order Markov Models (HOMMs). A second-order model looks at the last two states; a third-order looks at the last three. However, this leads to a "parameter explosion." If a website has $N$ pages, a first-order model requires $N^2$ transition probabilities. A third-order model requires $N^4$. For any real-world system, this quickly becomes computationally impossible and leads to massive overfitting.

To solve this, researchers have developed "Goldilocks" models that capture long-term dependencies without the exponential cost:

  1. Linear Additive Markov Processes (LAMP): Ravi Kumar and Andrew Tomkins proposed LAMP, which models the next state as a weighted mixture of transitions from all past states. This provides long-range memory while remaining as efficient as a first-order chain.
  2. Retrospective Higher-Order Markov Processes (RHOMP): David F. Gleich and Tao Wu introduced RHOMP, which assumes users "look back" at a specific past state to decide their next move. This keeps parameter growth linear rather than exponential.
  3. Higher-Order Networks (HONs): Mandana Saebi and Nitesh Chawla developed BuildHON+, an algorithm that represents systems as networks where nodes represent variable-length paths. This allows the model to capture higher-order dependencies only where they actually exist in the data, ignoring them where the Markov assumption holds true.

Applications: From Baskets to Bioportal

This shift toward higher-order modeling is transforming how we predict sequential behavior across domains:

  • Recommendation Systems: Traditional "next-item" recommenders often focus only on the last item viewed. Ruining He and Julian McAuley argue in Translation-based Recommendation that capturing long-term user intent requires moving beyond these local transitions. Similarly, Shengxian Wan uses neural networks to capture how purchases made several steps back influence current needs in "Next Basket" prediction.
  • Human Mobility: In urban travel, the entire history of a day's visits influences the next choice. Qingjie Liu and Yixuan Zuo developed the Travel Time Difference Model, which uses the context of the entire trip path to identify intended destinations more accurately than memoryless models.
  • Knowledge Exploration: By analyzing logs from BioPortal, Simon Walk and Denis Helić identified distinct "behavioral personas." They proved that first-order models miss the multi-step intentions of users navigating complex hierarchical ontologies, where the path taken through the tree is as important as the current node.

Conclusion

The research direction is clear: while first-order Markov models are a useful starting point, they are insufficient for capturing the nuance of human intent. By using multi-order generative models like MOGen (Christoph Gote) or context-aware embeddings (Jianzhong Qi), we can build systems that understand not just where a user is, but where they are going based on where they have been.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_higher_order_modeling_for_non_markovian__05a97aae,
  title = {Higher-Order Modeling for Non-Markovian Sequential Data},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/higher-order-modeling-for-non-markovian-sequential-data/rdr_05a97aae199040a585d92573603624ab},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_higher_order_modeling_for_non_markovian__05a97aae_v1,
  title = {Higher-Order Modeling for Non-Markovian Sequential Data},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/higher-order-modeling-for-non-markovian-sequential-data/rdr_05a97aae199040a585d92573603624ab/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}