← All publications
BETA This research page is an early version. Explanatory text, figure selection, and presentation are still being revised.
UAI 2026 ORAL 🏆 Best Paper Award

Fundamental Limits and Optimal Methods for Sharp Analytical Causal Bounds in Instrumental Variable Models

Arefe Boushehrian* · Mohammad Reza Badri* · Sina Akbari · Negar Kiyavash
* Equal contribution.
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence · 2026
Paper GitHub UAI / PMLR Slides
Keywords.
instrumental variables partial identification sharp bounds causal inference

TL;DR.

Sharp analytical instrumental-variable bounds cannot stay simple as the outcome alphabet grows. We prove that any sharp bound needs exponentially many linear pieces, and the same exponential barrier appears in the IV inequalities. We also give Python and R procedures that attain this optimal complexity.

Why this matters.

It establishes a genuine complexity barrier for sharp analytical IV bounds: exponential structure is unavoidable. The accompanying algorithms match that lower bound, so the result says both what is impossible and what is optimal.

Abstract

Bounding causal effects analytically, rather than numerically, is appealing for its interpretability and conceptual clarity. Existing sharp methods rely on optimization-based approaches such as the Balke–Pearl framework, whose computational complexity grows rapidly. An alternative line of work derives bounds heuristically using probability laws and generic inequalities, and some recent papers have claimed or conjectured that this approach can yield sharp analytical bounds with substantially lower complexity. In this paper, we show that this perceived advantage is illusory. In particular, in a discrete instrumental variable setting, we show that any sharp analytical bound for the average treatment effect must be expressible as a maximum (minimum) over a collection of linear terms whose cardinality grows exponentially in the number of values taken by the outcome. In parallel, we show that the number of instrumental variable inequalities itself also grows exponentially. Consequently, bounds and inequalities expressed using only polynomially many such terms cannot be sharp. As a constructive complement, the paper is accompanied by codes implemented in python and R to derive sharp analytical bounds and sharp inequalities with optimal computational complexity, matching the lower bounds proven in this paper. These codes are available online.

Main message. The key point is both negative and positive. We show that exact sharpness has an unavoidable exponential price, but we also show how to avoid paying anything beyond that price.

The paper at a glance

An informal guide to the problem, the idea, and the main results.

binary treatment D outcome Y with n values instrument Z with ℓ values sharp bounds IV inequalities

1. The problem

Analytical IV bounds are attractive because they are transparent. But classical optimization-based methods become expensive, and it was unclear whether that was only an algorithmic artifact or a fundamental barrier.

2. The key idea

We express the sharp-bound and sharp-testing problems through the geometry of dual polyhedra and cones. For a binary instrument, that geometry can be characterized combinatorially, giving direct generation algorithms instead of generic vertex enumeration.

3. Main result

Informal result For a binary instrument (ℓ = 2), the sharp ATE bound has exactly 5·4^(n−1) − 2^(n+2) + 4 linear pieces, where n is the number of outcome values.

So even in the binary-instrument case, the sharp formula grows exponentially in the outcome support n.

4. Another result

Another informal result For a binary instrument (ℓ = 2), a complete non-redundant IV test needs exactly 2^(n+1) − 4 inequalities, again with n denoting the outcome-support size.

For general ℓ-valued instruments, we prove corresponding exponential lower bounds, where ℓ is the number of instrument values.

5. How it works

  1. Write the IV model and the target ATE as linear optimization problems.
  2. Dualize the problems to expose the relevant vertices and extreme rays.
  3. Characterize those objects combinatorially when the instrument is binary (ℓ = 2).
  4. Generate the sharp bound pieces and IV inequalities directly, in time linear in the output size.

What the experiments show

Main empirical message.

Our direct construction is not only output-optimal in theory; it is dramatically faster in computation. In the runtime comparison, our method is already more than 1,000× faster than causaloptim at outcome support size n = 6. At n = 7, our implementation takes milliseconds while causaloptim takes more than 24 hours, even though both return the same exact sharp bounds.

>1,000×faster than causaloptim at n = 6
millisecondsour runtime at n = 7
>24 hourscausaloptim runtime at n = 7
Log-scale runtime comparison between causaloptim and the direct sharp-bound generation method as outcome support size increases.
Runtime comparison from Figure 1 of the paper. The direct construction scales with the unavoidable output size, while generic vertex enumeration becomes much more expensive.

Where this helps

Good fit

  • You want exact sharp analytical IV bounds rather than purely numerical bounds for one dataset.
  • You need a complete explicit characterization of the IV model's testable implications.
  • You want software that automatically derives the full set of sharp bounds and IV inequalities.
  • You care about what is fundamentally impossible and what is algorithmically optimal.

Keep in mind

  • For binary instruments, we give the complete explicit characterization together with software that generates the sharp ATE bounds and IV inequalities directly.
  • For multi-valued instruments, we establish general exponential lower bounds that rule out polynomial-size exact linear characterizations.

Cite this paper

@InProceedings{pmlr-v337-boushehrian26a,
  title     = {Fundamental Limits and Optimal Methods for Sharp Analytical Causal Bounds in Instrumental Variable Models},
  author    = {Boushehrian, Arefe and Badri, Mohammad Reza and Akbari, Sina and Kiyavash, Negar},
  booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence},
  pages     = {689--744},
  year      = {2026},
  volume    = {337},
  series    = {Proceedings of Machine Learning Research},
  publisher = {PMLR},
  url       = {https://proceedings.mlr.press/v337/boushehrian26a.html}
}