# Lattice Annotated Temporal (LAT) Logic for Non-Markovian Reasoning

arXiv: https://arxiv.org/abs/2509.02958 · HTML: https://mlsanity.com/paper/2509.02958/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 23 of its 65 references that are in the map.
- First posted on arXiv 3 Sep 2025.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 23 of 23)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Logic-LM: Empowering Large Language Models with Symbolic Solvers for Faithful Logical Reasoning](https://mlsanity.com/paper/2305.12295/) (2023)
- [StarCraft II: A New Challenge for Reinforcement Learning](https://mlsanity.com/paper/1708.04782/) (2017)
- [Learning Explanatory Rules from Noisy Data](https://mlsanity.com/paper/1711.04574/) (2017)
- [Logical Neural Networks](https://mlsanity.com/paper/2006.13155/) (2020)
- [Reinforcement Learning with Non-Markovian Rewards](https://mlsanity.com/paper/1912.02552/) (2019)
- [Turning 30: New Ideas in Inductive Logic Programming](https://mlsanity.com/paper/2002.11002/) (2020)
- [Ontology Reasoning with Deep Neural Networks](https://mlsanity.com/paper/1808.07980/) (2018)
- [Neuro-Symbolic Inductive Logic Programming with Logical Neural Networks](https://mlsanity.com/paper/2112.03324/) (2021)
- [Differentiable Inductive Logic Programming for Structured Examples](https://mlsanity.com/paper/2103.01719/) (2021)
- [PyReason: Software for Open World Temporal Logic](https://mlsanity.com/paper/2302.13482/) (2023)
- [Reinforcement Learning for Joint Optimization of Multiple Rewards](https://mlsanity.com/paper/1909.02940/) (2019)
- [Reinforcement Learning in Non-Markovian Environments](https://mlsanity.com/paper/2211.01595/) (2022)
- [Extensions to Generalized Annotated Logic and an Equivalent Neural Architecture](https://mlsanity.com/paper/2302.12195/) (2023)
- [MANCaLog: A Logic for Multi-Attribute Network Cascades (Technical Report)](https://mlsanity.com/paper/1301.0302/) (2013)
- [Non-Markovian Reinforcement Learning using Fractional Dynamics](https://mlsanity.com/paper/2107.13790/) (2021)
- [Consistency-based Abductive Reasoning over Perceptual Errors of Multiple Pre-trained Models in Novel Environments](https://mlsanity.com/paper/2505.19361/) (2025)
- [On the complexity of Temporal Equilibrium Logic](https://mlsanity.com/paper/1503.00043/) (2015)
- [Sea-cret Agents: Maritime Abduction for Region Generation to Expose Dark Vessel Trajectories](https://mlsanity.com/paper/2502.01503/) (2025)
- [Deep Inductive Logic Programming meets Reinforcement Learning](https://mlsanity.com/paper/2308.16210/) (2023)
- [Machine Learning Model Integration with Open World Temporal Logic for Process Automation](https://mlsanity.com/paper/2506.17776/) (2025)
- [Reasoning about Medical Triage Optimization with Logic Programming](https://mlsanity.com/paper/2507.10781/) (2025)

## Abstract (arXiv)

We introduce Lattice Annotated Temporal (LAT) Logic, an extension of Generalized Annotated Logic Programs (GAPs) that incorporates temporal reasoning and supports open-world semantics through the use of a lower lattice structure. This logic combines an efficient deduction process with temporal logic programming to support non-Markovian relationships and open-world reasoning capabilities. The open-world aspect, a by-product of the use of the lower-lattice annotation structure, allows for efficient grounding through a Skolemization process, even in domains with infinite or highly diverse constants. We provide a suite of theoretical results that bound the computational complexity of the grounding process, in addition to showing that many of the results on GAPs (using an upper lattice) still hold with the lower lattice and temporal extensions (though different proof techniques are required). Our open-source implementation, PyReason, features modular design, machine-level optimizations, and direct integration with reinforcement learning environments. Empirical evaluations across multi-agent simulations and knowledge graph tasks demonstrate up to three orders of magnitude speedup and up to five orders of magnitude memory reduction while maintaining or improving task performance. Additionally, we evaluate LAT Logic's value in reinforcement learning environments as a non-Markovian simulator, achieving up to three orders of magnitude faster simulation with improved agent performance, including a 26% increase in win rate due to capturing richer temporal dependencies. These results highlight LAT Logic's potential as a unified, extensible framework for open-world temporal reasoning in dynamic and uncertain environments. Our implementation is available at: pyreason.syracuse.edu.