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:
- Deep Neural Networks: In safety verification, an input interval passes through thousands of interconnected neurons. If every intermediate layer treats its dependent internal signals as independent, the final output bounds explode. As Wang et al. demonstrate in Formal Security Analysis of Neural Networks using Symbolic Intervals, naive interval arithmetic yields bounds so wide they are practically useless for proving safety properties like collision avoidance. Nii et al. observed a similar "artificial expansion of uncertainty" when propagating fuzzy numbers through multi-layer architectures (Decreasing Excess Fuzziness Included in Fuzzy Output Vectors from Neural Networks).
- Engineering and Optimization: Whether solving fuzzy linear systems in structural analysis (Shariatmadar et al.), verifying global optimization problems (Allamigeon et al.), or computing valid parameter ranges (Grandón et al.), the inability to track variable correlations results in an accumulation of "excess width" that obscures the true mathematical boundaries.
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.