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

• URL: http://arxiv.org/abs/2509.02958v1
• Date: Wed, 03 Sep 2025 02:45:34 GMT
• Title: Lattice Annotated Temporal (LAT) Logic for Non-Markovian Reasoning
• Authors: Kaustuv Mukherji, Jaikrishna Manojkumar Patil, Dyuman Aditya, Paulo Shakarian, Devendra Parkar, Lahari Pokala, Clark Dorman, Gerardo I. Simari,
• Abstract summary: LAT Logic is an extension of Generalized Annotated Logic Programs (GAPs)<n>LAT Logic supports open-world semantics through the use of a lower lattice structure.<n>Our open-source implementation, PyReason, features modular design, machine-level optimizations, and direct integration with reinforcement learning environments.
• Score: 0.20878935665163192
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Do It for HER: First-Order Temporal Logic Reward Specification in Reinforcement Learning (Extended Version) [49.462399222747024]
  We propose a novel framework for the logical specification of non-Markovian rewards in Decision Processes (MDPs) with large state spaces.<n>Our approach leverages Linear Temporal Logic Modulo Theories over finite traces (LTLfMT)<n>We introduce a method based on reward machines and Hindsight Experience Replay (HER) to translate first-order logic specifications and address reward sparsity.
  arXiv  Detail & Related papers  (2026-02-05T22:11:28Z)
• Prism: Efficient Test-Time Scaling via Hierarchical Search and Self-Verification for Discrete Diffusion Language Models [96.0074341403456]
  Inference-time compute has re-emerged as a practical way to improve LLM reasoning.<n>Most test-time scaling (TTS) algorithms rely on autoregressive decoding.<n>We propose Prism, an efficient TTS framework for dLLMs.
  arXiv  Detail & Related papers  (2026-02-02T09:14:51Z)
• STReasoner: Empowering LLMs for Spatio-Temporal Reasoning in Time Series via Spatial-Aware Reinforcement Learning [16.11676643415448]
  patio-temporal reasoning in time series involves the explicit synthesis of temporal dynamics, spatial dependencies, and textual context.<n>This capability is vital for high-stakes decision-making in systems such as traffic networks, power grids, and disease propagation.<n>To address the gap, we introduce ST-Bench, a benchmark consisting of four core tasks, including etiological reasoning, entity identification, correlation reasoning, and in-context forecasting.<n>We then propose STReasoner, which empowers LLM to integrate time series, graph structure, and text for explicit reasoning.
  arXiv  Detail & Related papers  (2026-01-06T18:46:12Z)
• SYNAPSE: Empowering LLM Agents with Episodic-Semantic Memory via Spreading Activation [29.545442480332515]
  We introduce Synapse, a unified memory architecture that transcends static rather than pre-computed links.<n>We show that Synapse significantly outperforms state-of-the-art methods in complex temporal and multi-hop reasoning tasks.<n>Our code and data will be made publicly available upon acceptance.
  arXiv  Detail & Related papers  (2026-01-06T06:19:58Z)
• GLOW: Graph-Language Co-Reasoning for Agentic Workflow Performance Prediction [51.83437071408662]
  We propose GLOW, a unified framework for AW performance prediction.<n>GLOW combines the graph-structure modeling capabilities of GNNs with the reasoning power of LLMs.<n>Experiments on FLORA-Bench show that GLOW outperforms state-of-the-art baselines in prediction accuracy and ranking utility.
  arXiv  Detail & Related papers  (2025-12-11T13:30:46Z)
• WARP-LUTs - Walsh-Assisted Relaxation for Probabilistic Look Up Tables [0.0]
  Walsh-Assisted Relaxation for Probabilistic Look-Up Tables (WARP-LUTs)<n>We introduce WARP-LUTs - a novel gradient-based method that efficiently learns combinations of logic gates with substantially fewer trainable parameters.<n>We demonstrate that WARP-LUTs achieve significantly faster convergence on CIFAR-10 compared to DLGNs, while maintaining comparable accuracy.
  arXiv  Detail & Related papers  (2025-10-17T13:44:36Z)
• GRIL: Knowledge Graph Retrieval-Integrated Learning with Large Language Models [59.72897499248909]
  We propose a novel graph retriever trained end-to-end with Large Language Models (LLMs)<n>Within the extracted subgraph, structural knowledge and semantic features are encoded via soft tokens and the verbalized graph, respectively, which are infused into the LLM together.<n>Our approach consistently achieves state-of-the-art performance, validating the strength of joint graph-LLM optimization for complex reasoning tasks.
  arXiv  Detail & Related papers  (2025-09-20T02:38:00Z)
• T-ILR: a Neurosymbolic Integration for LTLf [47.316620315732024]
  We propose a neurosymbolic framework to incorporate temporal logic specifications directly into deep learning architectures for sequence-based tasks.<n>We name this proposed method Temporal Iterative Local Refinement (T-ILR)
  arXiv  Detail & Related papers  (2025-08-21T20:24:20Z)
• Do LLMs Dream of Discrete Algorithms? [0.7646713951724011]
  Large Language Models (LLMs) have rapidly transformed the landscape of artificial intelligence.<n>Their reliance on probabilistic inference limits their effectiveness in domains requiring strict logical reasoning.<n>This paper proposes a neurosymbolic approach that augments LLMs with logic-based reasoning modules.
  arXiv  Detail & Related papers  (2025-06-29T22:03:01Z)
• Learning Efficient and Generalizable Graph Retriever for Knowledge-Graph Question Answering [75.12322966980003]
  Large Language Models (LLMs) have shown strong inductive reasoning ability across various domains.<n>Most existing RAG pipelines rely on unstructured text, limiting interpretability and structured reasoning.<n>Recent studies have explored integrating knowledge graphs with LLMs for knowledge graph question answering.<n>We propose RAPL, a novel framework for efficient and effective graph retrieval in KGQA.
  arXiv  Detail & Related papers  (2025-06-11T12:03:52Z)
• PixelThink: Towards Efficient Chain-of-Pixel Reasoning [70.32510083790069]
  PixelThink is a simple yet effective scheme that integrates externally estimated task difficulty and internally measured model uncertainty.<n>It learns to compress reasoning length in accordance with scene complexity and predictive confidence.<n> Experimental results demonstrate that the proposed approach improves both reasoning efficiency and overall segmentation performance.
  arXiv  Detail & Related papers  (2025-05-29T17:55:49Z)
• Efficient FPGA Implementation of Time-Domain Popcount for Low-Complexity Machine Learning [0.2663045001864042]
  Population count (popcount) is a crucial operation for many low-complexity machine learning (ML) algorithms.<n>We propose an innovative approach to accelerate and optimize these operations by performing them in the time domain.
  arXiv  Detail & Related papers  (2025-05-04T16:44:15Z)
• Optimizing LLM Inference: Fluid-Guided Online Scheduling with Memory Constraints [14.341123057506827]
  Large Language Models (LLMs) are indispensable in today's applications, but their inference procedure demands significant computational resources.<n>This paper formulates LLM inference optimization as a multi-stage online scheduling problem.<n>We develop a fluid dynamics approximation to provide a tractable benchmark that guides algorithm design.
  arXiv  Detail & Related papers  (2025-04-15T16:00:21Z)
• LASE: Learned Adjacency Spectral Embeddings [9.227991604045416]
  We learn nodal Adjacency Spectral Embeddings (ASE) from graph inputs.<n>LASE is interpretable, parameter efficient, robust to inputs with unobserved edges.<n>LASE layers combine Graph Convolutional Network (GCN) and fully-connected Graph Attention Network (GAT) modules.
  arXiv  Detail & Related papers  (2024-12-23T17:35:19Z)
• Improving Complex Reasoning over Knowledge Graph with Logic-Aware Curriculum Tuning [89.89857766491475]
  We propose a curriculum-based logical-aware instruction tuning framework, named LACT.<n>Specifically, we augment the arbitrary first-order logical queries via binary tree decomposition.<n> Experiments across widely used datasets demonstrate that LACT has substantial improvements(brings an average +5.5% MRR score) over advanced methods, achieving the new state-of-the-art.
  arXiv  Detail & Related papers  (2024-05-02T18:12:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.