Tracking Variable Dependencies in Interval Arithmetic

28 concepts18 papers1 proposal

Imagine you are computing the range of a simple function, $f(x) = x - x$, where the uncertain variable $x$ is known to lie within the interval $[1, 2]$.

If you evaluate this using standard interval arithmetic, you treat the first occurrence of $x$ and the second occurrence of $x$ as completely independent entities. The calculation becomes $[1, 2] - [1, 2]$, which yields the interval $[-1, 1]$.

But mathematically, we know that $x - x = 0$ for any real number. The true range is simply $[0, 0]$. The interval has artificially inflated because the system "forgot" that both terms must point to the exact same value at any given moment.

This phenomenon is known as the dependency problem (or the multi-occurrence problem). It is the fundamental bottleneck of interval-based reasoning. When a single uncertain variable appears multiple times within an expression or a computational graph, standard interval arithmetic loses track of the correlations between those instances, leading to an overestimation of the output range.

The Cost of Independence in Complex Systems

As early as 1987, Sacks identified this issue as a primary limitation in automated inequality provers, noting that treating multiple occurrences of the same variable as independent yields overly pessimistic or physically impossible bounds (Hierarchical Reasoning about Inequalities). Soon after, Lhomme formalized how this lack of coordination weakens the pruning power of consistency algorithms in numeric constraint satisfaction problems (Consistency Techniques for Numeric CSPs).

When computations are chained together in modern applications, this overestimation compounds exponentially:

To solve this, researchers have developed three primary paradigms: tracking correlations symbolically, exploiting global function properties, and modeling statistical couplings.

Solution 1: Tracking Correlations Symbolically

The most direct way to solve the dependency problem is to upgrade the underlying number representation so that intervals carry their operational history with them.

Affine Arithmetic and Taylor Models

Instead of representing an uncertain value as a flat interval $[a, b]$, Affine Arithmetic represents quantities as a linear combination of a central value and shared, independent "noise symbols" ($\epsilon_i \in [-1, 1]$).

For example, if two different intermediate variables, $x$ and $y$, both depend on the same underlying source of uncertainty, they might be written as: $$x = 10 + 2\epsilon_1$$ $$y = 5 + 2\epsilon_1$$

If an algorithm computes $x - y$, it evaluates: $$(10 + 2\epsilon_1) - (5 + 2\epsilon_1) = 5$$

Because both variables share the symbol $\epsilon_1$, the uncertainty perfectly cancels out. Ceberio et al. demonstrated that this tracking mechanism dramatically reduces excess width in automated expert systems (Interval-Type and Affine Arithmetic-Type Techniques for Handling Uncertainty in Expert Systems).

For highly non-linear systems, Taylor models extend this concept by approximating functions using higher-order polynomials combined with a small interval remainder to bound the truncation error. Althoff et al. implemented these models within the CORA reachability analyzer to maintain tight, rigorous bounds for cyber-physical verification where variables frequently interact and cancel out (Implementation of Taylor models in CORA 2018; see also Implementation of Interval Arithmetic in CORA 2016). Modern unified frameworks like RangeEnclosures.jl leverage these advanced representations alongside branch-and-bound methods to systematically compute tight enclosures (Ferranti et al.).

Solution 2: Exploiting Monotonicity and Derivatives

An alternative to tracking symbols throughout a computation is to analyze the global geometry of the function itself. If we know how a function behaves across an entire domain, we can bypass step-by-step interval evaluation entirely.

Monotonicity Filtering

If a function is strictly increasing or strictly decreasing with respect to a multi-occurrence variable, the dependency problem vanishes. For a monotonic function $f(x)$, the true minimum and maximum will always occur precisely at the endpoints of the interval domain of $x$.

Araya 0001 et al. exploited this property by introducing the Monotonic Hull Consistency (Mohc) algorithm (Exploiting Monotonicity in Interval Constraint Propagation). By identifying monotonic sub-expressions within non-linear constraints, Mohc injects global boundary information directly into standard interval propagation loops, achieving tighter variable bounds and significant computational speedups.

The Mean Value Form

When functions are non-monotonic, their variations can be bounded using derivatives. The mean value form evaluates a function at a single exact midpoint $c$ of an interval, and then bounds the remaining variation by multiplying the interval derivative by the distance from that midpoint: $$f(X) \subseteq f(c) + f'(X)(X - c)$$

Because the derivative $f'(X)$ captures the functional relationship of how the output changes relative to the input, this second-order approximation naturally accounts for internal dependencies. Schollmeyer et al. utilized this approach via "neighboring derivatives" to prevent the artificial inflation of uncertainty bands in interval-dependent regression models (Neural network model for imprecise regression with interval dependent variables).

Solution 3: Statistical and Copula-Based Coupling

The dependency problem also manifests when aggregating probabilistic or possibilistic intervals. For instance, if you sum multiple individual prediction intervals to estimate a total value, simply adding the bounds assumes a worst-case scenario where every single error aligns perfectly in the same direction.

To resolve this without falling back on overly conservative worst-case assumptions, recent frameworks incorporate explicit correlation structures:

  • Symmetric Calibration: In conformal prediction, Luo et al. introduced Conformal Interval Arithmetic, which utilizes a symmetric calibration technique to account for the underlying correlations between individual prediction errors, allowing for tight, mathematically guaranteed intervals for aggregate metrics (Conformalized Interval Arithmetic with Symmetric Calibration).
  • Copulas: In risk analysis and possibilistic calculus, Gray et al. integrated copulas—statistical functions used to describe the linkages between variables independent of their marginal distributions (Dependent Possibilistic Arithmetic using Copulas). By injecting these precise correlation structures directly into the arithmetic, the authors provided a way to prevent the over-conservative widening of uncertainty bounds, making interval-based risk models sharp enough to inform high-stakes engineering decisions.

Key Foundational Work

Hierarchical Reasoning about Inequalities (1987) — contributed 2 concept elements to this direction.
Consistency Techniques for Numeric CSPs (1993) — contributed 2 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 18 papers
  2. Version 1 · 2026-10-04 · 27 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_interval_dependency_problem_98d7c5aa,
  title = {interval dependency problem},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/interval-dependency-problem/rdr_98d7c5aaa86d470a909eb638792660c8},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_interval_dependency_problem_98d7c5aa_v2,
  title = {interval dependency problem},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/interval-dependency-problem/rdr_98d7c5aaa86d470a909eb638792660c8/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake