You are viewing a plain text version of this content. The canonical link for it is here.
Posted to discuss-archive@tvm.apache.org by "jinhongyii (via GitHub)" <gi...@apache.org> on 2026/06/04 00:20:33 UTC
[PR] [Arith] Memoize IntervalSet variable relaxation to avoid exponential blowup [tvm]
jinhongyii opened a new pull request, #19670:
URL: https://github.com/apache/tvm/pull/19670
## Problem
`Analyzer::Bind` could hang indefinitely (>300s, ~200% CPU, no GPU work) while binding a small expression for one variable. The root cause is general and lives in `src/arith/int_set.cc`.
Diagnosis: 100% of the time is spent in `arith::Analyzer::Bind` → `IntSetAnalyzer` → `IntervalSetEvaluator`, evaluating a **5-node** bound expression. A counter showed **>2^20 `VisitExpr` calls at recursion depth 67** with no end in sight.
## Root cause
`IntervalSetEvaluator::VisitExpr_(VarNode)` relaxes a variable's bounds by recursively evaluating **both** the `min` and `max` sub-expressions of its mapped interval. For diamond-shaped variable dependency chains (`a → {b, c}`, `b → {d, e}`, …) the shared sub-expressions are re-expanded along every path, so cost is **O(2^depth)** in the length of the dependency chain — bounded only by `dom_map_.size()` (~67 interdependent vars in the failing case).
## Fix
Memoize the fully-relaxed interval **per variable** (`relax_memo_`) and break cyclic dependencies with an in-progress set (`relax_in_progress_`). A variable's relaxed interval is deterministic for a given evaluator instance (`dom_map_`/`dom_constraints_` are fixed), so memoizing collapses the diamonds to linear cost. Short chains — the common case, which never reached the old `recur_depth_ >= dom_map_.size()` cutoff — are unaffected, so the change is behavior-preserving outside the pathological case.
## Tests
New regression tests in `tests/python/arith/test_arith_intset.py`:
- `test_relax_deep_variable_dependency_chain` — a 64-deep diamond (`O(2^64)` without the fix; verified to hang on a clean build), also asserting the relaxed result is correct (`x0 → [-n, 100+n]`).
- `test_relax_cyclic_variable_dependency` — a cyclic `x↔y` dependency must terminate.
## Verification
- `tests/python/arith/test_arith_intset.py` — 20 passed (the deep-chain test completes instantly).
- Full `tests/python/arith/` — 933 passed (1 pre-existing flaky random-seed failure in `test_arith_solve_linear_equations.py` unrelated to this change, passes on rerun).
🤖 Generated with [Claude Code](https://claude.com/claude-code)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: discuss-archive-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: discuss-archive-unsubscribe@tvm.apache.org
For additional commands, e-mail: discuss-archive-help@tvm.apache.org
Re: [PR] [Arith] Memoize IntervalSet variable relaxation to avoid exponential blowup [tvm]
Posted by "tqchen (via GitHub)" <gi...@apache.org>.
tqchen merged PR #19670:
URL: https://github.com/apache/tvm/pull/19670
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: discuss-archive-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: discuss-archive-unsubscribe@tvm.apache.org
For additional commands, e-mail: discuss-archive-help@tvm.apache.org
Re: [PR] [Arith] Memoize IntervalSet variable relaxation to avoid exponential blowup [tvm]
Posted by "gemini-code-assist[bot] (via GitHub)" <gi...@apache.org>.
gemini-code-assist[bot] commented on code in PR #19670:
URL: https://github.com/apache/tvm/pull/19670#discussion_r3352682601
##########
tests/python/arith/test_arith_intset.py:
##########
@@ -394,5 +394,35 @@ def test_modular_set():
)
+def test_relax_deep_variable_dependency_chain():
+ """Regression test for exponential variable-relaxation blowup.
+
+ When a variable's interval bound references another variable that is also in
+ the domain map, the evaluator relaxes it transitively. A diamond-shaped
+ chain -- where each variable's bound references the next one in *both* its
+ min and its max -- used to be re-expanded along every path, costing
+ O(2^depth) and hanging indefinitely. The relaxation is now memoized per
+ variable, so this completes in linear time.
+ """
+ ck = IntSetChecker()
+ n = 64 # 2^64 expansions without memoization; trivially fast with it.
+ xs = [tvm.tirx.Var(f"x{i}", "int32") for i in range(n + 1)]
+ dmap = {xs[i]: tvm.arith.IntervalSet(xs[i + 1] - 1, xs[i + 1] + 1) for i in range(n)}
+ dmap[xs[n]] = tvm.arith.IntervalSet(0, 100)
+ # x0 relaxes through the whole chain: [0 - n, 100 + n].
+ ck.verify(xs[0], dmap, (-n, 100 + n))
+
+
+def test_relax_cyclic_variable_dependency():
+ """A cyclic variable dependency must terminate (and stay symbolic)."""
+ ana = tvm.arith.Analyzer()
+ x = tvm.tirx.Var("x", "int32")
+ y = tvm.tirx.Var("y", "int32")
+ # x depends on y and y depends on x: relaxation must not loop forever.
+ dmap = {x: tvm.arith.IntervalSet(y, y), y: tvm.arith.IntervalSet(x, x)}
+ res = ana.int_set(x, dmap)
+ assert res is not None
Review Comment:

Instead of just asserting `res is not None`, we can use the existing `IntSetChecker` helper to verify that the cyclic dependency correctly terminates and resolves to the expected symbolic interval `(y, y)`. This makes the test assertion much stronger and more precise.
```suggestion
def test_relax_cyclic_variable_dependency():
"""A cyclic variable dependency must terminate (and stay symbolic)."""
ck = IntSetChecker()
x = tvm.tirx.Var("x", "int32")
y = tvm.tirx.Var("y", "int32")
# x depends on y and y depends on x: relaxation must not loop forever.
dmap = {x: tvm.arith.IntervalSet(y, y), y: tvm.arith.IntervalSet(x, x)}
ck.verify(x, dmap, (y, y))
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: discuss-archive-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: discuss-archive-unsubscribe@tvm.apache.org
For additional commands, e-mail: discuss-archive-help@tvm.apache.org
Re: [PR] [Arith] Memoize IntervalSet variable relaxation to avoid exponential blowup [tvm]
Posted by "jinhongyii (via GitHub)" <gi...@apache.org>.
jinhongyii commented on PR #19670:
URL: https://github.com/apache/tvm/pull/19670#issuecomment-4617854964
cc: @tqchen
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: discuss-archive-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: discuss-archive-unsubscribe@tvm.apache.org
For additional commands, e-mail: discuss-archive-help@tvm.apache.org