Granularity-Typed Stream Reasoning: Remembering Old Data at the Resolution Rules Need

Rule-based monitors for drones, turbines and weather stations must answer questions that span very different time scales. "The motor temperature spiked within the last two seconds" and "the battery has been in a degraded state on most days this week" may appear in the same rulebook. Today's stream reasoners cut the incoming data into a sliding window, a fixed-length slice of recent history that is re-examined as new data arrives, and they store that window at a single clock resolution. If the window is long enough for the week-scale rule, it holds hundreds of thousands of second-level readings that no rule will ever look at in detail again. If it is short enough to be cheap, the week-scale rule silently gives wrong answers.

We propose that each predicate in a temporal rule program declare its own time resolution, or granularity: seconds for raw temperature, minutes for "overheating episode", days for "degraded battery day". Fine facts are then turned into coarse facts only through two explicit summary operators, "held throughout the granule" and "held at some point in the granule". With these declarations, a static analysis of the rules can determine, for every predicate, how far back and at what resolution the stream engine must remember it. Memory then grows with the sum of per-predicate horizons measured in each predicate's own units, not with the longest horizon measured in the finest clock ticks. The streaming answers remain exactly equal to what a batch reasoner would compute over the entire history.

Core Claim

The claim is that multi-scale temporal semantics, which have mostly been developed for offline reasoning, supply the missing retention policy for sliding-window reasoning. Concretely, we will extend DatalogMTL, a rule language with metric past and future operators such as "P held throughout the last $[a,b]$ time units", with per-predicate granularities and the two summary operators. We will prove that a stream engine which keeps predicate $p$ only for its analysed horizon $h_p$ at granularity $\Delta_p$ returns the same answers as full-history batch evaluation of the same program. We will then show that this retention scheme reduces memory and per-step latency substantially on programs that mix short and long horizons over noisy signals.

The memory comparison is simple to state. With chronon $\delta$ as the finest clock tick and $H=\max_p h_p$ as the longest horizon, a single-resolution window stores on the order of $\sum_p H/\delta$ time points. The typed engine stores $\sum_p h_p/\Delta_p$.

The gain is not automatic. When signals are piecewise constant, interval coalescing (merging adjacent intervals with the same fact into one) already compresses fine-grained storage, and in that case the typed engine should win little. We expect the gain in the regime coalescing cannot handle: flickering, noisy sensor predicates that must nevertheless feed long-horizon rules. The evaluation is built to locate that boundary rather than assume it away.

Relation to Prior Work

Two lines of work motivate the gap from opposite sides.

On the streaming side, Answer Update for Rule-Based Stream Reasoning maintains conclusions across window slides by shifting the validity of intact deductions and retracting those whose support expired. An Adaptive Framework for RDF Stream Reasoning formalises windows by a length and a slide size. The neural-symbolic tracker of A Scalable Reasoning and Learning Approach for Neural-Symbolic Stream Fusion and An Adaptive Semantic Stream Reasoning Framework for Deep Neural Networks runs incremental answer-set solving over frame-level windows at 15–30 frames per second. All of these use one uniform clock and one window extent. We reuse their incremental update primitives but apply them separately at each granularity level.

On the multi-scale side, A Common-Sense Theory of Time and Short Time Periods introduce "moments": periods that act as points at a coarse scale but have interval structure when magnified. An Algebra of Granular Temporal Relations for Qualitative Reasoning gives sound point-to-interval collapse rules. Reasoning and Acting in Time argues that only stabilised, boundary-crossing changes should reach coarse layers. These papers supply our semantics, in particular the justification that "throughout" and "somewhere" summaries preserve before, after and during relations under collapse. However, they are offline or purely algebraic.

The same offline limitation holds for the neural multi-granularity systems, Multi-granularity Temporal Question Answering over Knowledge Graphs and Time-aware ReAct Agent for Temporal Knowledge Graph Question Answering. Both index a complete historical graph in advance. They show that explicit granularity aggregation helps, but they offer no retention mechanism.

The closest bridging work constrains our design. Temporal Coalescing on Window Extents over Data Streams coalesces tuples inside sliding windows. It uses timestamp vectors to split merged intervals when constituents expire, and shows an out-of-order penalty for eager coalescing. It works at one granularity with relational value-equivalence and no rules. We take its lesson that eager structures are fragile under late data and confine eager maintenance to the currently open granule at each level.

Practical Reasoning in DatalogMTL provides the MeTeoR engine: seminaïve materialisation with coalescing, which answered 99.7% of queries without its automata fallback at up to 397 million facts. MeTeoR explicitly lacks retraction for live streams and has a single timeline unit. Explaining Critical Situations Over Sensor Data Streams Using Proofs and Natural Language runs an 85-rule drone-safety DatalogMTL program on MeTeoR, but only offline, and it leaves sliding windows to future work. Its rulebase is our most realistic test program.

Research Program

The first component is the language and its analysis. Each predicate $p$ carries a granularity $\Delta_p$ drawn from a nested hierarchy, such as second, minute, hour and day. A rule may use a finer predicate $q$ in the body of a coarser head only through $\mathrm{All}_{\Delta}(q)$ or $\mathrm{Some}_{\Delta}(q)$. $\mathrm{All}_{\Delta}(q)$ is true on granule $g$ if $q$ holds at every fine point of $g$; $\mathrm{Some}_{\Delta}(q)$ is true if $q$ holds at least once in $g$. Metric operator intervals in a rule must be multiples of the rule's granularity.

The analysis then computes, for each predicate, the largest past lookback at which any rule reads it, in that predicate's own units. This is a backward pass over the rule dependency graph, and it is where the per-predicate horizon $h_p$ comes from. We will prove equivalence with batch semantics for programs with bounded past operators. Future operators, which MeTeoR handles with a separate safety net, are restricted to bounded forms, and each is given a pending placeholder in the manner of formula progression.

The second component is the incremental engine, built on MeTeoR's materialiser. At each granularity level, facts in the currently open granule are maintained eagerly. When the granule closes, its $\mathrm{All}$ and $\mathrm{Some}$ summaries are emitted upward, and fine facts older than their horizon are evicted using the shift-and-retract update from answer-update reasoning. Out-of-order arrivals that land in an open granule cost nothing extra. Arrivals that land in an already closed granule trigger a bounded repair: that granule's summaries are recomputed and the change is propagated upward. Because the repair scope is one granule per level, we expect the cost of late data to scale with the number of levels rather than with window length. This is the direct contrast with the split-and-recoalesce cost that timestamp vectors incur.

The third component is a set of mixed-horizon benchmark programs. The 85-rule drone program will be extended with hour- and day-level rules for cumulative wear. The Weather Benchmark from MeTeoR will receive rules pairing minute-level gust conditions with multi-day heat-wave conditions. The Intel Berkeley Research Lab sensor stream, with 2.3 million readings, will receive analogous rules. The iTemporal generator will be used to sweep the ratio between the longest and shortest horizon and the flicker rate of base predicates.

These programs are authored by us, which is a threat to validity. We mitigate it by releasing them and by reporting results as a function of the controlled iTemporal sweep, not only on hand-picked programs.

Baselines

The naive reference point is periodic batch recomputation. On each slide, MeTeoR materialises the full program from scratch over the entire history so far, with the summary operators compiled into ordinary rules. This is the correctness oracle for every other system. It also shows the unbounded-growth cost that motivates streaming. MeTeoR's reported 99.7% forward-materialisation success and its 397-million-fact scale (Practical Reasoning in DatalogMTL) tell us it is a strong oracle on static data. We found no reported result on Lacuna for MeTeoR's per-slide latency or memory on a live stream, so we will measure it ourselves.

The strongest existing competitor is a single-resolution incremental sliding window. It uses a window of length $H$ at the finest chronon, maintained with the answer-update primitives of Answer Update for Rule-Based Stream Reasoning, and applies MeTeoR's interval coalescing inside the window. For out-of-order data, it uses the eager/lazy assignment of Temporal Coalescing on Window Extents over Data Streams. It is exact by construction, so any win on our side must come from memory and latency, not accuracy. No reported result was found on Lacuna for this combination on our benchmarks. Its individual components report no streaming numbers in the file: the coalescing paper reports trends rather than latency figures on the Intel data.

Both systems will be implemented in the same Python codebase on top of MeTeoR, run on the same machine, fed the same stream replay with the same injected disorder, and given the same effort in tuning buffer sizes. Beating this baseline means matching its answers exactly while using at least several times less peak memory and lower median and tail per-slide latency. The comparison is made in the high-flicker regime. We also require the typed engine to be no worse in the low-flicker regime.

The key ablation is per-predicate horizons without granularity. This single-chronon engine uses our analysis to evict each predicate after its own horizon but never summarises to a coarser granule. It separates the benefit of the retention analysis alone from the benefit of multi-scale summarisation. If this ablation captures most of the gain, the multi-scale part of our proposal is unnecessary, and we will say so.

A second ablation keeps granularities but stores only $\mathrm{Some}$ summaries. It measures how many long-horizon "throughout" rules then become underivable, which tests whether the two-summary design is actually needed.

Why not just…?

Why not just use one fine-grained window long enough for the longest rule and rely on coalescing? This is the most serious threat. When base predicates change rarely, coalescing turns an hour of constant "flying" into a single interval, and the fine window costs almost nothing. The evidence against it holds only for flickering signals. There, coalescing yields one fact per flicker, and a long "throughout" operator must scan all of them. Our flicker-rate sweep on iTemporal-generated programs will show where the two curves cross. If there is no crossing within the flicker rates seen in the real Intel and Weather streams, the proposal's practical value is limited to a clean semantics, and we will report that.

Why not just pre-aggregate the stream to a coarse rate before reasoning? Downsampling to minute averages makes the week-scale rules cheap but destroys the second-level rules. The drone program's overheating and handover rules in Explaining Critical Situations Over Sensor Data Streams Using Proofs and Natural Language fire on short spikes. Averaging also has no guaranteed relationship to "throughout" or "somewhere", so answers change in unanalysable ways. We will run this baseline and report its precision and recall against the oracle, which we expect to be poor on fine-horizon rules.

Why not just run two separate reasoners, a fast one and a slow one, with hand-written glue? This is roughly what engineers do today. It amounts to our design without the analysis or the equivalence guarantee. The glue must decide by hand what to pass upward and how long to keep it, which is exactly where silent truncation errors appear. We will build the two-reasoner version for the drone program, count its disagreements with the oracle under disorder, and compare engineering effort measured as lines of glue code. If it proves as accurate and as fast, our contribution reduces to automating it, which is a smaller but still real claim.

Why not just stream the data to a language model? Off-the-shelf models handle long numeric sequences poorly: GPT-4.1 reaches 35.9% on causality discovery versus 64.0% for a specialised model (TimeOmni-1). Such models also provide no exactness guarantee, which a safety monitor requires. We therefore do not treat this as a competitor for the core question.

Proposed Experiments

The decisive check is exactness together with savings. On the extended drone program, the Weather Benchmark and the Intel stream, every answer of the typed engine must match the batch oracle at every slide. Any mismatch falsifies the equivalence theorem or its implementation. We will then report peak retained facts, median and 99th-percentile per-slide latency, and throughput against the single-resolution incremental baseline and the horizon-only ablation.

The second check uses the iTemporal sweep over horizon ratio (1 to $10^5$) and base-predicate flicker rate. It should show gains growing with both, and near-parity when flicker is low. If gains appear at low flicker, that would suggest a measurement artefact.

The third check concerns disorder. We will inject late arrivals at rates from 0 to 30% and delays up to several coarse granules, and measure repair cost. We expect it to stay roughly flat in window length, whereas the eager-coalescing baseline should degrade as Temporal Coalescing on Window Extents over Data Streams reports.

Finally, we will measure the overhead of the analysis and the number of rules that fail granularity type-checking in the drone program as written. This tells us how much rewriting real rulebases need before they can benefit.