Identity Testing for Circuits with Exponentiation Gates

Now we describe our identity testing algorithms in the simplified setting. First, we show that a simple randomized algorithm with one query works in the real query model. The algorithm is to randomly sample $\overrightarrow{x}\in {[B]}^n$ for $B=20\cdot d\cdot k^2$ and accepts if $P(\overrightarrow{x})\in \{0,\perp \}$. It is clear that the algorithm is perfectly complete, and the soundness is given by the following theorem:

As the second result, we analyze the following simple randomized identity testing algorithm in the algebraic query model: Let $p,q,G$ be defined as above, the algorithm randomly samples $\overrightarrow{u}\in {𝔽}_p^n$, $\overrightarrow{v}\in {𝔽}_q^n$, and $a\in G$, and accepts if $P_a(\overrightarrow{u},\overrightarrow{v})\in \{0,\perp \}$. The following theorem formalizes the completeness and soundness of the algorithm:

Note that for sufficiently large $k,q\in \mathbb{N}$ such that $\ln q\le k-1$, we have

Thus in a typical setting that $d{k}^3\le q\le k^{O(1)}$, the soundness error is $1-\mathrm{\Theta }(\log k/(k-1))$.³³3The error probability is constant if $q$ is exponential in $k$. However, this setting is not meaningful: The width $k$ is usually comparable to the input length, and thus the arithmetic operations over $q$ would be extremely inefficient. By parallel repetition of the randomized algorithm for $O(k\log k/\log q)$ times, we can boost the error probability to $1/k^{O(1)}$. This leads to an efficient randomized identity testing algorithm when $k$ is relatively small and the evaluation is much more efficient than obtaining the description of $P(\overrightarrow{x})$, which, in particular, captures the real-world constraints for the optimization compilers such as Mirage [25].

We briefly explain our circuit model (called ${\mathrm{𝖠𝖤𝗑𝗉}}^1$ circuits) and refer readers to Sections 3 and 4 for more details. We work with (arithmetic) circuits with integer coefficients, unbounded fan-in addition and multiplication gates, fan-in two division gates, and fan-in one exponentiation gates. In addition, we impose the restriction that on each path from input variables to output gates, there is at most one exponentiation gates – the circuit cannot compute double exponential $x\mapsto e^{e^x}$ by composing exponentiation gates.

The evaluation of circuits over real numbers is defined by a standard gate-by-gate evaluation algorithm, where the exponentiation gate is interpreted as the function $x\mapsto e^x$. However, it is unclear how to define the evaluation of such circuits over finite fields, as there is no standard interpretation of the exponential function.

Let $p$ be a prime number. To define the evaluation of an ${\mathrm{𝖠𝖤𝗑𝗉}}^1$ circuit $C$ over ${𝔽}_p$, a natural idea is to replace the exponential function by $x\mapsto a^x$ for some element $a\in {𝔽}_p$. This is not ideal as such an interpretation is inconsistent with the evaluation over $ℝ$: It could be the case that

for $x_1,x_2\in {𝔽}_p$, while $e^{x_1+x_2}=e^{x_1}{e}^{x_2}$ for any $x_1,x_2\in ℝ$. As a result, this definition cannot be used for the identity testing of ${\mathrm{𝖠𝖤𝗑𝗉}}^1$ circuits.

To address the issue, we exploit the algebraic structure of finite fields by using different moduli over and under the exponents. Let $p,q$ be prime numbers such that $q\mid p-1$, $G\subseteq {𝔽}_p^{\ast }$ be the unique order-$q$ multiplicative subgroup, and $a\in G$. It follows that

for any $x_1,x_2\in {𝔽}_q$. If we use $q$ as the modulus “over the exponent” and $p$ as the modulus “under the exponent”, the function $x\mapsto a^x$ will be consistent with the arithmetic law $e^{x_1+x_2}=e^{x_1}\cdot e^{x_2}$. Following the intuition, we define the evaluation of $C$ with respect to $(p,q,a)$ using a gate-by-gate evaluation algorithm such that:

• $\mathrm{■}$

  Each input variable or wire carries a pair $(u,v)\in ({𝔽}_p\cup \{\perp \})\times ({𝔽}_q\cup \{\perp \})$.

• $\mathrm{■}$

  Addition, multiplication, and division gates are implemented coordinate-wisely.

• $\mathrm{■}$

  The exponentiation gate is implemented by $(u,v)\mapsto (a^{v}modp,\perp )$.

This evaluation algorithm can be implemented efficiently given the description of the circuit $C$. We refer readers to Section 3 for more details.

Let $\overrightarrow{u}=(u_1,\mathrm{\dots },u_n)\in {𝔽}_p^n$, $\overrightarrow{v}=(v_1,\mathrm{\dots },v_n)\in {𝔽}_q^n$, we use $C_a(\overrightarrow{u},\overrightarrow{v})$ to denote the output of the evaluation algorithm where the $i$-th input variable is assigned to $(u_i,v_i)$. Similar to the standard results that algebraic circuits compute polynomials [2, Section 16], we can then prove that ${\mathrm{𝖠𝖤𝗑𝗉}}^1$ circuits can be converted to an equivalent fraction of exponential polynomials:

We stress that the structural lemma does not provide a polynomial upper bound on the degree, width, or integer weight of the integer-coefficient exponential polynomials $P,P^{\prime }$. Nevertheless, it can be verified that the exponential polynomials $P,P^{\prime }$ for ${\mathrm{𝖠𝖤𝗑𝗉}}^1$ circuits from real-world neural network applications, such as $\mathrm{𝗌𝗈𝖿𝗍𝗆𝖺𝗑}(\cdot )$ and Attention with softmax activations [23], tend to have relatively small degree, width, and weight; interested readers are referred to Section 4.5 for more discussion, and [25] for experimental results.

Let ${\mathrm{𝖽𝗈𝗆}}_{ℝ}(C)$ be the domain of the circuit $C$, i.e., the set of $\overrightarrow{x}\in {ℝ}^n$ such that $C(\overrightarrow{x})\ne \perp$. An ${\mathrm{𝖠𝖤𝗑𝗉}}^1$ circuit $C$ is said to have degree $d$, width $k$, and weight $w$ if there are integer-coefficient degree-$d$ width-$k$ exponential polynomials $P(\overrightarrow{x})$ and $P^{\prime }(\overrightarrow{x})$ with all integer coefficients within $[-w,w]$ that satisfy Lemma 6.

By generalizing Theorems 4 and 5 to fractions of exponential polynomials and combining them with Lemma 6, we can obtain the final result:

The idea behind Theorem 4 is very simple: We manage to combine the Schwartz-Zippel lemma and Lindemann-Weierstrass theorem, i.e., $e$ is transcendental (see Theorem 13).

To avoid technical subtlety, we assume that $P(\overrightarrow{x})$ is a degree-$d$ exponential polynomial where the exponent fractions $g_i(\overrightarrow{x})/h_i(\overrightarrow{x})$ are pairwisely distinct; that is, for every pair of indices $i,j\in [k]$, $i\ne j$, $g_i(\overrightarrow{x})h_j(\overrightarrow{x})-g_j(\overrightarrow{x})h_i(\overrightarrow{x})$ is not a zero polynomial. Such an exponential polynomial is said to be condensed, and the general case can be reduced to the condensed case by considering another exponential polynomial $\widehat{P}$ that “groups” coefficients based on the exponent fraction; see Section 4.3. Moreover, we assume without loss of generality that $f_i\ne 0$ and $h_i\ne 0$ for each $i\in [k]$.

Let $S\subseteq \mathbb{Q}$ be a non-empty finite set, we know by the Schwartz-Zippel lemma that for any $i\in [k]$, $j\in [k]$, $i\ne j$, each of the following non-zero polynomials of degree at least $2d$

evaluates to zero with probability at most $2d/|S|$ for a uniformly random $\overrightarrow{x}\in S^n$. By the union bound, we can further prove that with probability at least $1-3d{k}^2/|S|$, none of the polynomials evaluate to $0$. For each of such $\overrightarrow{x}$, we can see that for the rational numbers ${\alpha }_i\triangleq g_i(\overrightarrow{x})/h_i(\overrightarrow{x})$ and ${\beta }_i\triangleq f_i(\overrightarrow{x})$, we have

which must be non-zero as $e$ is transcendental.

Unwinding the proof of Theorem 4, we could actually give a necessary and sufficient condition for an exponential polynomial with integer weights to be identically zero over real evaluations. Let $P(\overrightarrow{x})$ be a condensed degree-$d$ exponential polynomial

with integer coefficients, then $P(\overrightarrow{x})$ is identically zero on its domain (over real evaluation) if and only if for every $i\in [k]$, $f_i=0$. Subsequently, if $p,q$ are chosen to be larger than the integer coefficients, the identity testing of a condensed exponential function $P(\overrightarrow{x})$ is equivalent to testing whether $f_i=0(modp)$ for every $i\in [k]$.

With the characterization above, the completeness of Theorem 5 is relatively simple, so we will focus on the soundness property.

We try to mimic the strategy in the proof of Theorem 4. Suppose that $P(\overrightarrow{x})$ is not identically zero on real evaluations, we know by the discussion above that when $p$ are sufficiently large, there is at least one $f_i\ne 0(modp)$ for any $i\in [k]$. Moreover, if $q$ is sufficiently large, we know that for any $i\ne j$, $g_i{h}_j-g_j{h}_i\ne 0(modq)$. Assume without loss of generality that $f_i\ne 0$ for all $i\in [k]$. For $\overrightarrow{u}\in {𝔽}_p^n$ and $\overrightarrow{v}\in {𝔽}_q^n$ sampled uniformly at random, we still know by the Schwartz-Zippel lemma and the union bound that with probability at least $1-3d{k}^2/q$, none of

evaluates to zero for $i,j\in [k]$, $i\ne j$. We can then define ${\alpha }_i\triangleq g_i(\overrightarrow{x})/h_i(\overrightarrow{x})modq$ and ${\beta }_i\triangleq f_i(\overrightarrow{x})modp$ for $i\in [k]$ such that

where ${\beta }_1,\mathrm{\dots },{\beta }_k$ are non-zero and ${\alpha }_1,\mathrm{\dots },{\alpha }_k$ are pairwisely distinct.

It then suffices to prove that for any non-zero ${\beta }_1,\mathrm{\dots },{\beta }_k\in {𝔽}_p$ and distinct ${\alpha }_1,\mathrm{\dots },{\alpha }_k\in {𝔽}_q$, $k\ge 1$, if we sample $a\in G$ uniformly at random, the probability that ${\beta }_1{a}^{{\alpha }_1}+\mathrm{\dots }{\beta }_k{a}^{{\alpha }_k}modp=0$ is at most $q^{-1/(k-1)}$. We note that this can be viewed as a generalization of the Descartes’ Rule (see also [11]), which asserts that any univariate polynomial with $k$ monomials has at most $2k$ roots.

We provide an elementary proof of a weaker result: The probability that ${\beta }_1{a}^{{\alpha }_1}+\mathrm{\dots }{\beta }_k{a}^{{\alpha }_k}modp=0$ is at most $1-1/k$. Theorem 5 is proved using a lemma from [11], which employs a similar but slightly more complicated argument.

Recall that the order-$q$ multiplicative subgroup $G\subseteq {𝔽}_p^{\ast }$ is a cyclic group. For any fixed $i\in {𝔽}_q$, a random element $a\in G$ can be viewed as generated from randomly sampling $g\in G$ and outputting $g^i$. Our idea is to choose a good $i\in {𝔽}_q$ such that at least a $1/k$ fraction of $g$ satisfies that ${\beta }_1{g}^{i\cdot {\alpha }_1}+\mathrm{\dots }{\beta }_k{g}^{i\cdot {\alpha }_k}modp\ne 0$.

We say that an index $i\in {𝔽}_q$ is good for $\alpha \in {𝔽}_q$ if $i\cdot \alpha modq\le (1-1/k)\cdot q$, and is said to be good if for every $j\in [k]$, $i$ is good for ${\alpha }_i$. It turns out that if there is a good $i\in {𝔽}_q$,

can be viewed as a polynomial in ${𝔽}_p[g]$ of degree at most $(1-1/k)\cdot q$; in that case, there are at most $(1-1/k)\cdot q$ roots in ${𝔽}_p$ (and also in $G$).

Therefore, it remains to prove the existence of a good $i$. Since $i\mapsto i\cdot \alpha$ is a bijection in ${𝔽}_q$, we know that for any fixed $\alpha$, the probability that a random $i\in {𝔽}_q$ is good for $\alpha$ is at least $1-1/k$. By the union bound, we know that a random $i\in {𝔽}_q$ is good for ${\alpha }_1,\mathrm{\dots },{\alpha }_k$ with non-zero probability. This implies that there must be a good $i\in {𝔽}_q$, which completes the proof.

There are a few technical issues to obtain the main theorem (see Theorem 7).

First, the proof overview above assumes that the exponential polynomial is condensed, i.e., its exponent fractions are pairwisely distinct. For exponential polynomials that are not condensed, we need to first condense the polynomial by merging terms with equivalent exponent fractions. For instance, the following exponential polynomial $P(\overrightarrow{x})=\exp \left(\frac{x^2-3x}{x-3}\right)+\exp \left(\frac{x^2-2x}{x-2}\right)$ may be condensed to $\widehat{P}(\overrightarrow{x})=2\exp \left(\frac{x^2-3x}{x-3}\right)$. In general, such condensation procedure results into another exponential polynomial $\widehat{P}$ that has larger domain and agree with $P$ on the domain of $P$ (see Proposition 19). We need to bridge the gap between $P$ and $\widehat{P}$ with standard probability analysis.

Second, as shown in Section 1.2, ${\mathrm{𝖠𝖤𝗑𝗉}}^1$ circuits are converted to fractions $P/P^{\prime }$ of exponential polynomials rather than exponential polynomials. This requires a careful (but straightforward) adaption of the techniques above. In particular, in the soundness analysis, we use the observation that $P/P^{\prime }$ is identically zero on its domain (over $ℝ$) if and only if the exponential polynomial $P\cdot P^{\prime }$ is identically zero on its domain (over $ℝ$). This leads to a quadratic overhead (in $k$) in the soundness error of Theorem 7 compared to Theorem 5, as $P\cdot P^{\prime }$ may have width up to $k^2$ when both $P$ and $P^{\prime }$ are of width $k$.

We review basic definitions and classical results that we will need in Section 2. In Section 3, we formally describe our circuit model as well as the query models we considered in our paper – the idealized real query model and the algebraic query model; we also briefly explain why the algebraic query model is a better abstraction in the application of optimization compilers for neural networks. In Section 4, we define exponential polynomials, discuss its basic properties, and prove the structural lemma that converts circuits to fractions of exponential polynomials. In Section 5, we prove the correctness of our probabilistic testing algorithm in the real and algebraic query models.

It is also interesting to consider whether we can design better identity testing algorithms for some restricted classes of ${\mathrm{𝖠𝖤𝗑𝗉}}^1$ circuits (e.g. of small constant depth). This would potentially lead to real-world applications, as the structure of circuits from neural networks is relatively simple. To start with, one may consider adapting existing techniques for identity testing of algebraic circuits (see, e.g., [17, 18]) to ${\mathrm{𝖠𝖤𝗑𝗉}}^1$ circuits.

On the other hand, it is interesting to consider whether there are conditional or unconditional lower bounds for identity testing of ${\mathrm{𝖠𝖤𝗑𝗉}}^1$ circuits in black-box models, such as the algebraic query models that we introduced in Section 1.2.

We note the the algebraic query model in Section 1.2 is not necessarily the only reasonable formalization of the real world problem. Recall that in optimization compilers for neural networks [24, 25], the neural network (modeled by an ${\mathrm{𝖠𝖤𝗑𝗉}}^1$ circuit) is loaded into specialized devices (such as GPU or TPU) that are optimized for specific computation patterns and have high communication overhead with the CPU. Algorithms in other black-box models are potentially useful for real-world applications if:

1. 1.

   the queries can be efficiently implemented on those specialized devices; and

2. 2.

   the communication overhead is small.

We are not aware of other natural models that satisfies these constraints for identity testing of ${\mathrm{𝖠𝖤𝗑𝗉}}^1$ circuits, and it remains an interesting open problem that may require joint efforts of system and theory communities. Note that it may make it possible to design better identity testing algorithms if we work with another black-box query model that has better mathematical properties.

The evaluation of ${\mathrm{𝖠𝖤𝗑𝗉}}^1$ circuits over real numbers should be clear through the definition. Let $C$ be any $n$-input ${\mathrm{𝖠𝖤𝗑𝗉}}^1$ circuit and $\overrightarrow{x}\in {ℝ}^n$, the evaluation of $C(\overrightarrow{x})$ is defined as the output of the output gate, where the output values of gates are defined by gate-by-gate evaluation following a topological order.

In particular, if the divisor of a division gate is zero, $C(\overrightarrow{x})$ is undefined. Therefore, an ${\mathrm{𝖠𝖤𝗑𝗉}}^1$ circuit may compute a partial function $C:{ℝ}^n\to ℝ$. We define the domain of a $C(\overrightarrow{x})$ circuit on $ℝ$, denoted by ${\mathrm{𝖽𝗈𝗆}}_{ℝ}(C)$, as the set of $\overrightarrow{x}\in {ℝ}^n$ such that $C(\overrightarrow{x})$ is defined. For any $\overrightarrow{x}\notin {\mathrm{𝖽𝗈𝗆}}_{ℝ}(C)$, we may also say $C(\overrightarrow{x})=\perp$.

Our circuit model is a straightforward formalization of the program representation in Mirage [25]. Intuitively, the motivation to introduce ${\mathrm{𝖠𝖤𝗑𝗉}}^1$ circuit is to model components that are widely used in model artificial neural networks that consist of non-linear activation functions.

Let $p,q$ be two primes such that $q\mid p-1$, and $G_{p,q}$ be the (unique) multiplicative subgroup of ${𝔽}_p^{\ast }$ of order $q$. Equivalently, $G_{p,q}$ contains the roots of the univariate polynomial $z^q-1$ over ${𝔽}_p$. Loosely speaking, we will define the evaluation of $C$ on the input $(\overrightarrow{u},\overrightarrow{v})\in {𝔽}_p^n\times {𝔽}_q^n$ and $a\in G_{p,q}$ (modulo $(p,q)$) by

• $\mathrm{■}$

  interpreting the exponentiation gate by the function $x\mapsto a^{x}modp$,

• $\mathrm{■}$

  implementing all computation “on the exponent” in ${𝔽}_q$,

• $\mathrm{■}$

  implementing all computation “under the exponent” in ${𝔽}_p$,

and evaluating the circuit gate by gate.

We use $C_a(\overrightarrow{u},\overrightarrow{v})$ to denote the evaluation above; see the full version for its formal definition.

Similar to the evaluation of ${\mathrm{𝖠𝖤𝗑𝗉}}^1$ circuits on $ℝ$, $C_a(\overrightarrow{u},\overrightarrow{v})$ may be undefined, denoted by $C_a(\overrightarrow{u},\overrightarrow{v})=\perp$, due to division-by-zero. For each $a\in G_{p,q}$, we define the domain of $C$ with respect to $a$ modulo $(p,q)$, denoted by ${\mathrm{𝖽𝗈𝗆}}_{p,q,a}(C)$, as $\{(\overrightarrow{u},\overrightarrow{v})\in {𝔽}_p^n\times {𝔽}_q^n\mid C_a(\overrightarrow{u},\overrightarrow{v})\ne \perp \}$.

Subsequently, we define the identity testing problem for an ${\mathrm{𝖠𝖤𝗑𝗉}}^1$ circuit $C$ over the algebraic query model as follows. Let $p,q,G_{p,q}$ be specified above. The algorithm for identity testing is allowed to query the following oracle:

• $\mathrm{■}$

  (Evaluation). Given $(\overrightarrow{u},\overrightarrow{v})\in {𝔽}_p^n\times {𝔽}_q^n$ and $a\in G_{p,q}$, the oracle reports $C_a(\overrightarrow{u},\overrightarrow{v})\in {𝔽}_p\cup \{\perp \}$.

This query model is efficient both theoretically and practically. It can be observed, for instance, that the oracle in the algebraic query model can be implemented by algorithms in $O(s\cdot (\log p+\log q))$ space and polynomial time. In practice, the simplicity of the evaluation model makes it possible to implement it in the neural network compiler scenario (see [24, 25] for more details).

We can view $P(\overrightarrow{x})$ as a function $P(\cdot ):{ℝ}^n\to ℝ$ as follows. Given an input $\overrightarrow{u}\in {ℝ}^n$, the evaluation of $P(\overrightarrow{x})$ on the input $\overrightarrow{u}$ is defined as

where all the operators (i.e., additions, divisions, multiplications, and exponentiations) are interpreted as corresponding functions in $ℝ$. If for some $i\in [k]$, $h_i(\overrightarrow{u})=0$, the exponential polynomial is said to be undefined on $\overrightarrow{u}$. The domain of $P(\overrightarrow{x})$ over $ℝ$, denoted by ${\mathrm{𝖽𝗈𝗆}}_{ℝ}(P)$, is defined as ${\mathrm{𝖽𝗈𝗆}}_{ℝ}(P)\triangleq \{\overrightarrow{u}\in {ℝ}^n\mid h_i(\overrightarrow{u})\ne 0\forall i\in [k]\}$.

Similar to the algebraic query model for ${\mathrm{𝖠𝖤𝗑𝗉}}^1$ circuits, we require two finite fields for the computation under and over exponents to define the evaluation of $P$ over finite fields. Let $p,q$ be two primes such that $q\mid p-1$, and $G_{p,q}$ be the multiplicative subgroup of ${𝔽}_p^{\ast }$ of order $q$. Given inputs $\overrightarrow{u}\in {𝔽}_p^n,\overrightarrow{v}\in {𝔽}_q^n$, and $a\in G_{p,q}$, the evaluation of $P$ on $\overrightarrow{u}$ and $\overrightarrow{u}$, denoted by $P_a(\overrightarrow{u},\overrightarrow{v})$, is defined as:

Note that $P_a(\overrightarrow{u},\overrightarrow{v})$ is undefined, denoted by $P_a(\overrightarrow{u},\overrightarrow{v})=\perp$, if $h_i(\overrightarrow{v})modq=0$ for some $i\in [k]$. The domain of $P(\overrightarrow{x})$ over $(p,q,a)$ is defined as