← All papers
First page of Fixing the Fixpoint: A Formal Theory of Convergence Detection for Incremental Recursive Computation

Fixing the Fixpoint: A Formal Theory of Convergence Detection for Incremental Recursive Computation

Chengxi Yang, Tej Chajed, Thomas Reps

cs.PL Sep 30, 2026 · v1 cs.DB
All results are mechanized in Lean 4, porting a Lean 3 DBSP formalization (2,095 lines) and adding 11,748 lines on convergence detection.
Modern incremental computation theories like DBSP have enabled efficient incrementalization of general recursive computations. To do so, they require a runtime Fixpoint Detection (FPD) mechanism to detect whether an iterative computation has reached the fixpoint and thus should terminate. However, we show that the commonly suggested "FirstZero" strategy is unsound even in naturally arising cases, and that exact FPD is impossible for arbitrary DBSP circuits with expressive primitive nodes. This issue reveals a fundamental gap between the mathematical specification and implementations of such theories. To fill this gap, using DBSP as a core calculus, we develop a formal theory of convergence detection. Within this theory, we define internal convergence (IntConv) as a declarative criterion corresponding to the internal-state-stability strategy used by practical implementations, and prove that IntConv is a sufficient condition for external convergence. We then define the state fixpoint (StFP) predicate and a sound and complete StFP detector. Combining the StFP detector with fixed-input and zero-output checks yields a sound and complete IntConv detector. Moreover, for a large class of useful circuits (programs) including Datalog queries, nested while queries, and their incrementally optimized versions, we show that IntConv is not only sound but also complete (meaning any convergence in the theory implies the convergence in our criterion). As a result, our theory provides semantic guarantees for convergence detection on all these circuits. Our results are formally verified in Lean, with the formalization available at https://github.com/Arcadia-Y/fixing-the-fixpoint/.

Incremental computation frameworks like DBSP need runtime fixpoint detection to terminate iterative computations. The common FirstZero strategy is unsound, and exact fixpoint detection is impossible for arbitrary DBSP circuits, leaving a gap between theory and implementations.

Using DBSP as a core calculus with streams of level 1 or 2, the authors define internal convergence (IntConv), which matches the internal-state-stability strategy used by implementations such as Feldera. They prove IntConv sufficient for external convergence. They then build a sound and complete state-fixpoint (StFP) detector and combine it with fixed-input and zero-output checks. All definitions and proofs are mechanized in Lean 4, including a Hoare logic framework and Zset circuit case studies.

IntConv is sound in general and complete for regular circuits, which include Datalog and nested while queries. Completeness is preserved by DBSP's incremental optimizations (plift, incOpt). The Lean development totals about 13.8k lines.