Pith. sign in

REVIEW 3 major objections 7 minor 15 references

Tensor Evolution: A Framework for Fast Evaluation of Tensor Computations using Recurrences

T0 review · 3 major / 7 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper claims that loop-carried tensor computations can be represented as tensor recurrences and rewritten into closed-form expressions, generalizing scalar chain-of-recurrences to tensors.

desk verdict Nice extension of SCEV to tensors, but the central rewrite rules have counterexamples, so the framework's claims outrun the evidence. read the letter →

arxiv 2502.03402 v2 pith:MDH6AP5U submitted 2025-02-05 cs.PL cs.MS

Javed Absar , Samarth Narang , Muthu Baskaran This is my paper · ORCID
classification cs.PLcs.MS
keywords tensorevolutionchainofrecurrencesscalarloopoptimizationclosed-formevaluationcompilersrewriterulesML/HPC
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper argues that tensor computations carried across loop iterations can be represented as tensor recurrences and then algebraically rewritten into closed-form expressions, so a compiler can compute the final value without running the loop. The idea generalizes the chain-of-recurrences technique that already underpins scalar induction-variable analysis in mainstream compilers. The payoff is concrete: loops that accumulate slices or reshapes of evolving tensors, common patterns in machine learning and high-performance code, could be replaced by a direct formula. The paper demonstrates this with a loop that adds a constant tensor to $x$, slices off one row, and accumulates it into $y$, rewriting its output as $Y_k = Y_0 + k\,S(X_0) + \frac{k(k+1)}{2}\,S(A)$.

What carries the argument

The central object is the tensor evolution expression, a chain of recurrences lifted from scalars to tensors: $\{T_{c_0}, \odot_1, T_{c_1}, \odot_2, \dots, \odot_k, \tau_k\}$ evaluates by applying the element-wise operators $\odot_i$ to a seed tensor and successive tensor-valued terms. The load-bearing mechanism is a set of rewrite lemmas stating that tensor operations such as reshape, slice, concatenation, and broadcast commute with the evolution structure, so they can be pulled outside the recurrence braces. Once inside the braces, the chain can be unfolded into a closed-form polynomial or closed-form expression in the loop counter, exactly as classical chain-of-recurrences rewriting turns a scalar recurrence into a polynomial.

What would settle it

Use the paper's own loop with random tensors and compare its output against $Y_0 + k\,S(X_0) + \frac{k(k+1)}{2}\,S(A)$ for several $k$ and shapes; then repeat with the slice $x[1,:]$ replaced by an overlapping slice such as $x[0:2,:]$. If the formula no longer matches the loop, the slice lemma's commutation with the recurrence is false, and the closed-form claim collapses.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is that scalar chain-of-recurrences notation has a tensor analogue: a basic tensor evolution tuple $\{T_c, \odot, \tau_1\}$ denotes the value $T_c \odot \tau_1(1) \odot \cdots \odot \tau_1(i)$ after $i$ iterations, and a chain of evolutions nests such tuples. The paper proposes rewrite lemmas for element-wise addition and multiplication, addition of a loop-invariant tensor, reshape, slice, concatenation, broadcast, and injection of one evolution into another, claiming these preserve the evolution's meaning. Applying the lemmas to a loop that repeatedly updates $x \leftarrow x + a$ and accumulates the slice $x[1,:]$ into $y$ yields the closed form $Y_k = Y_0 + k\,S(X_0) + \frac{k(k+1)}{2}\,S(A)$, where $S$ denotes the slice operation. This, the paper argues, lets the loop's exit value be computed directly, in the same way scalar evolution computes loop-exit values of induction variables.

Load-bearing premise

The argument rests on the assumption that its unproved rewrite lemmas, especially multiplication of two evolving tensors and moving reshape, slice, concatenation, and broadcast outside a recurrence, are sound for all loop-invariant tensors and loop-variant functions, including tensors whose shapes change or whose slices overlap, so if any of these rules fails in such cases, the closed-form result would not hold.

Editorial extensions

If this is right

  • A tensor loop whose updates are element-wise additions or multiplications, possibly followed by reshape, slice, or concatenation, can have its exit value expressed as a closed form in the loop counter.
  • Compilers can use the closed form to skip the loop entirely, reducing the loop's cost to a single tensor computation or to the cost of evaluating the formula.
  • The rewrite rules give tensor loops an analogue of scalar induction-variable strength reduction, replacing an accumulator computed every iteration by a direct update.
  • The framework is intentionally partial: only computations that admit a recurrence simplification are reduced, and the paper does not claim all tensor expressions in loops are amenable.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A natural next step the paper does not develop is handling reduction operations, which it lists as a tensor op but does not give lemmas for; reductions over an evolving axis might be rewritten as closed-form sums or dot products.
  • If the lemmas hold under broadcasting with unequal shapes, the same machinery could optimize patterns that combine broadcast, slice, and element-wise products in a loop, since those are exactly the operations the lemmas target.
  • The framework suggests a testable compiler pass: detect loops whose tensor updates fit a TeV pattern, derive the closed form, and compare numerical outputs against the original loop on random inputs to validate the rewrite in practice.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 7 minor

Summary. Tensor Evolution (TeV) is proposed as a tensor analogue of Scalar Evolution and Chains of Recurrences. After reviewing CR and SCEV, the paper defines a basic tensor evolution {Tc, ⊙, τ1} in Eq. (1), introduces chains of evolution, and states rewrite lemmas (Lemmas 7–13, summarized in Table 1) for reshape, slice, concat, broadcast, and element-wise arithmetic. The main application is a worked loop example in which y accumulates x[1,:] while x is updated by adding a; using the slice and chain rules the paper derives Yk = Y0 + k*S(X0) + k(k+1)/2*S(A). The paper claims this enables closed-form evaluation without iterating, and it surveys related work in tensor compilers and polyhedral frameworks.

Significance. The idea of extending CR-based scalar evolution to tensors is timely and relevant for ML/HPC compilers, and the paper's motivating example is instructive. The arithmetic in the Section 6 example is correct, and the paper honestly notes that not all computations are amenable to the transformation. However, the paper's central claim depends on the correctness and generality of its rewrite rules; two of the presented rules are false as stated, and none of the lemmas are proved. As it stands the paper is best read as a position/vision statement rather than a validated framework, and significant work is needed to turn it into a reliable compiler transformation.

major comments (3)
  1. [5 (Lemma 12)] Lemma 12 is not valid under the evaluation rule in Eq. (1). For constant tensors A=B=0 and τ1=τ2=1, the left-hand side at i=2 is (0+2)(0+2)=4, while the right-hand side {0, +, τ1{B,+,τ2} + τ2{A,+,τ1} + τ1τ2} evaluated with Eq. (1) gives 0 + Σ_{j=1}^{2}(2j+1) = 8. The rule becomes correct only if the subexpressions {B,+,τ2} and {A,+,τ1} inside the step are evaluated at j−1 rather than at j, and this index shift is never stated. The same issue affects the scalar Lemma 5. Since multiplication of evolving tensors is a core operation, this lemma must be corrected and proved.
  2. [Table 1 (concat rows)] The concat rewrite for mixed operators is false. Let A=B=[0], τ1=[1], τ2=[2], with the first TeV using '+' and the second using '*'. Under Eq. (1), the true concatenated value at i=2 is [2,0], but the rewritten expression {[0,0], +, [1,2]} evaluates to [2,4]. Lemma 10 as stated only covers the case where both TeVs use the same operator; Table 1 extends it to mixed operators without justification. Concatenation is a central tensor operation, so either the rows must be restricted to identical operators or a separate mixed-operator rule with its own side conditions must be proved.
  3. [Section 5 (Lemmas 7-13)] None of Lemmas 7–13 is proved, and the two counterexamples above show that the missing side conditions are not cosmetic. For each rewrite the paper must state exactly when it applies: shapes and broadcast semantics of K, A, B, τ1, τ2; the dimension along which concatenation or slicing occurs and whether the indices are loop-invariant; and the iteration index at which subexpressions inside a chain are evaluated. Without such a precise statement, a compiler implementing these rules would generate wrong code for the cases in Table 1, and the paper's claim that TeV 'can play a part in the optimization and analysis parts of ML and HPC compilers' is not supported.
minor comments (7)
  1. [Section 5/Table 1] The broadcast rows in Table 1 are introduced without a definition of broadcast or of its interaction with element-wise operators; please add a formal semantics and state the shape conditions under which the rewrite preserves the result.
  2. [Section 5 (Lemmas 8-9)] Lemmas 8 and 9 should state that the reshape/slice map is applied identically at every iteration and that any loop-variant slice indices or reshapes would invalidate the rewrite; the current informal wording leaves this implicit.
  3. [Section 6] The text says the interpretation is 'shown in 3', but no Figure 3 is present in the manuscript; please add the figure or correct the reference.
  4. [References] References [13] and [14] both point to the arXiv page of the Tensor Comprehensions paper instead of the PENCIL and Halide papers; please correct these URLs.
  5. [Section 5 (Lemma 13)] The arrow notation '{B, +, τ2} −→+ A' is never defined; please define it in terms of Eq. (1) or in a small-step semantics so that Lemma 13 can be checked.
  6. [Section 5 (Lemma 7)] The text 'see Fig. 7' in Lemma 7 appears to be a typo, as the manuscript has no Fig. 7.
  7. [Introduction/Related work] The novelty relative to the authors' prior technical talk [6] should be stated explicitly; currently the paper implies [6] presented part of the work but does not say which parts are new.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the tensor closed-form example is derived from the paper's stated rewrite rules and standard Chain of Recurrences evaluation, and the only self-references are tutorial/provenance notes that are not load-bearing.

full rationale

The central derivation in Section 6 converts the loop-carried tensor recurrence Yk = {Y0, +, S({X0, +, A})} into Yk = Y0 + k*S(X0) + k*(k+1)/2*S(A) via the paper's stated rewrite rules (slice, chain notation, and closed-form evaluation of an arithmetic-progression chain). This result is obtained from the recurrence and the standard Chain of Recurrences evaluation, not from any fitted parameter or from a quantity defined in terms of the target output, so it is not circular by construction. The tensor-specific rewrite lemmas (Lemmas 7-13) are stated as algebraic properties of the TeV definition; they are not imported from the authors' prior work. The only self-references are [5] (a tutorial on Scalar Evolution) and [6] (a prior technical talk on Tensor Evolution), used for background and provenance rather than as the justification for the tensor lemmas or the closed-form claim, so they are not load-bearing. Whether Lemma 12 and Table 1's concat rule are sound as written is a correctness concern, not a circularity concern; the example in Section 6 does not rely on those specific rules. Therefore the paper's claimed derivation is self-contained with respect to its inputs, and the circularity burden is minimal.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper introduces no free constants fitted to data and no new physical or empirical entities. The central assumptions are the external Chain of Recurrences theory and the unproved TeV rewrite lemmas.

assumptions (4)
  • standard math Correctness of the scalar Chain of Recurrences lemmas, including closed-form evaluation of CRs, as developed in Zima and Bachman et al.
    Used throughout Section 5 and the worked example; the paper does not re-derive CR theory.
  • domain assumption Loop-carried tensor updates can be expressed as elementwise recurrences over tensor entries with fixed shapes.
    The TeV definition in Equations 1 through 3 assumes each tensor value at iteration i is obtained by an elementwise operator applied to a loop-invariant tensor and a function over N; data-dependent shapes or control flow are not handled.
  • ad hoc to paper The rewrite rules in Lemmas 7 through 13 are sound.
    Stated without proof in Section 5; the worked example in Section 6 depends on these rules. If any rule has hidden shape or broadcast conditions, the derived closed form may not hold.
  • ad hoc to paper Structural tensor operations (reshape, slice, concat, broadcast) commute with elementwise recurrence evaluation in the manner asserted.
    Lemmas 8 through 10 and Table 1 assert these commutations; no proof or edge-case analysis, such as overlapping slices or dynamic broadcast shapes, is given.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Tensor Evolution: A Framework for Fast Evaluation of Tensor Computations using Recurrences." pith.science (2026). https://pith.science/paper/MDH6AP5U

@misc{pith2026250203402,
  author       = {Pith},
  title        = {Pith review of: Tensor Evolution: A Framework for Fast Evaluation of Tensor Computations using Recurrences},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MDH6AP5U}},
  note         = {Machine review of arXiv:2502.03402}
}
read the original abstract

This paper introduces a new mathematical framework for analysis and optimization of tensor expressions within an enclosing loop. Tensors are multi-dimensional arrays of values. They are common in high performance computing (HPC) and machine learning domains. Our framework extends Scalar Evolution - an important optimization pass implemented in both LLVM and GCC - to tensors. Scalar Evolution (SCEV) relies on the theory of `Chain of Recurrences' for its mathematical underpinnings. We use the same theory for Tensor Evolution (TeV). While some concepts from SCEV map easily to TeV -- e.g. element-wise operations; tensors introduce new operations such as concatenation, slicing, broadcast, reduction, and reshape which have no equivalent in scalars and SCEV. Not all computations are amenable to TeV analysis but it can play a part in the optimization and analysis parts of ML and HPC compilers. Also, for many mathematical/compiler ideas, applications may go beyond what was initially envisioned, once others build on it and take it further. We hope for a similar trajectory for the tensor-evolution concept.

Figures

Figures reproduced from arXiv: 2502.03402 by the authors.

Figure 1
Figure 1. Basic Tensor Evolution τ = {Tc0 , ⊙1, Tc1 , ⊙2, ..., ⊙k, τk} (2) which is defined recursively as τ (i) = {Tc0 , ⊙1, {Tc1 , ⊙2, ..., ⊙k, τk}}(i) (3) The operators ⊙i could all be the same (e.g., + or ∗) or different. Addi￾tionally, if we drop the braces and understand that the application of evolution proceeds from right to left, the chain of evolution can be rewritten simply as: τ (i) = {Tc0 , ⊙1, Tc1 , ⊙2, ..., ⊙k,… view at source ↗
Figure 2
Figure 2. Adding two TeV expressions Lemma 11 Adding two TeV Expressions Let {A, ⊙, τ1} and {B, ⊙, τ2} be two tensor evolution expressions (see [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Calculate tensor evolution expressions of given code. [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 9 canonical work pages

  1. [1]

    Pienaar and Mehdi Amini and Uday Bondhugula and River Riddle and Albert Cohen and Tatiana Sh- peisman and Andy Davis and Nicolas Vasilache and Oleksandr Zi- nenko

    Chris Lattner and Jacques A. Pienaar and Mehdi Amini and Uday Bondhugula and River Riddle and Albert Cohen and Tatiana Sh- peisman and Andy Davis and Nicolas Vasilache and Oleksandr Zi- nenko. MLIR: A Compiler Infrastructure for the End of Moore’s Law. https://arxiv.org/abs/2002.11054, 2021

    arXiv 2002

  2. [2]

    Glow: A Graph Lowering Compiler Techniques for Neural Networks

    Nadav Rotem and Jordan Fix and Saleem Abdulrasool and Summer Deng and Roman Dzhabarov and James Hegeman and Roman Levenstein and Bert Maher and Nadathur Satish and Jakob Olesen and Jongsoo Park and Artem Rakhov and Misha Smelyanskiy. Glow: A Graph Lowering Compiler Techniques for Neural Networks. http://arxiv.org/abs/1805.00907, 2018

    arXiv 2018

  3. [3]

    Py- Torch: An Imperative Style, High-Performance Deep Learning Library

    Adam Paszke and Sam Gross and Francisco Massa and Adam Lerer. Py- Torch: An Imperative Style, High-Performance Deep Learning Library. http://arxiv.org/abs/1912.01703, 2019

    arXiv 1912

  4. [4]

    TVM: An Automated End-to-End Optimizing Compiler for Deep Learning

    Tianqi Chen and Thierry Moreau and Ziheng Jiang and Lianmin Zheng. TVM: An Automated End-to-End Optimizing Compiler for Deep Learning. https://arxiv.org/abs/1802.04799, 2018

    arXiv 2018

  5. [5]

    Tutorial: Scalar Evolution - Demystified

    Javed Absar. Tutorial: Scalar Evolution - Demystified. 2018 LL VM Devel- opers Meeting

    work page 2018

  6. [6]

    Technical Talk: Tensor Evolution- An ML Graph Optimization Technique

    Javed Absar and Muthu Baskaran. Technical Talk: Tensor Evolution- An ML Graph Optimization Technique. 2023 LL VM Developers Meeting

    work page 2023

  7. [7]

    Jacob Devlin and Ming-Wei Chang and Kenton Lee and Kristina Toutanova. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Lin- guistics: Human Language Technologies, NAACL-HLT 2019, Minneapo- lis, MN, USA, June 2-7, 2019, Vol...

    doi:10.18653/v1/n19-1423 2019

  8. [8]

    Gomez and Lukasz Kaiser and Illia Polo- sukhin

    Ashish Vaswani and Noam Shazeer and Niki Parmar and Jakob Uszkoreit and Llion Jones and Aidan N. Gomez and Lukasz Kaiser and Illia Polo- sukhin. Attention is All you Need. Advances in Neural Information Pro- cessing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA

    work page 2017

Show all 15 references
  1. [9]

    Eugene V. Zima. Recurrent Relations and Speed-up of Computations Us- ing Computer Algebra Systems. = Design and Implementation of Symbolic Computation Systems, International Symposium, DISCO ’92, Bath, UK, April 13-15, 1992, Proceedings. Lecture Notes in Computer Science, vol-...

    1992

  2. [10]

    Computational Reduciblity, Wolfram Mathworld

    Stephen Wolfram. Computational Reduciblity, Wolfram Mathworld. https://mathworld.wolfram.com/ComputationalReducibility.html. 10

  3. [12]

    On Computational Properties of Chains of Recurrences

    Eugene Zima. On Computational Properties of Chains of Recurrences. ISSAC ’01: Proceedings of the 2001 international symposium on Symbolic and algebraic computation, 2001

    2001

  4. [14]

    Ragan-Kelley, C

    J. Ragan-Kelley, C. Barnes, A. Adams, S. Paris, F. Durand, and S. Amaras- inghe. Halide: a language and compiler for optimizing parallelism, locality, and recomputation in image processing pipelines. ACM SIGPLAN Notices, volume: 48(6), 2013. https://arxiv.org/pdf/1802.04730

    2013 arXiv

  5. [15]

    R. T. Mullapudi, V. Vasista, and U. Bondhugula. Polymage: Automatic optimization for image processing pipelines. Twentieth International Con- ference on Architectural Support for Programming Languages and Oper- ating Systems, ASPLOS ’15

  6. [16]

    Chains of Recurrences - a method to expedite the evaluation of closed-form functions

    Olaf Bachman, Paul Wang, Eugene Zima. Chains of Recurrences - a method to expedite the evaluation of closed-form functions. Proceedings of the international symposium on Symbolic and algebraic computation (ISAAC), volume: 15, 1994

    1994

  7. [17]

    Lethin and Allen Leung and Beno ˆ ıt Meister and P´ eter Szil´ agyi and Nicholas Vasilache and David Wohlford

    Richard A. Lethin and Allen Leung and Beno ˆ ıt Meister and P´ eter Szil´ agyi and Nicholas Vasilache and David Wohlford. R-Stream 3.0 Compiler. https://api.semanticscholar.org/CorpusID:198310344, 2008. 11

    2008

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.