DETAILED ACTION
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Response to Arguments
Applicant's arguments filed 12/08/2025 have been fully considered and they are considered persuasive.
Applicant’s arguments, with respect to the rejection(s) of claim(s) 1-8 and 10-20 under 35 U.S.C. § 103 have been fully considered and are persuasive. Therefore, the rejection has been withdrawn. However, upon further consideration, a new ground(s) of rejection is made in view of 35 U.S.C. § .
A new Examiner has been assigned to act on the application. Examiner has reviewed and given credit to the previous Examiner's actions consistent with MPEP § 704.01.
The following are the references previously relied upon and utilized in the rejections below:
Vaswani et al. “Attention Is All You Need” (2017)
Wang et al. “Linformer: Self-Attention with Linear Complexity” (2020)
Devlin et al. “BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding" (2019)
Allowable Subject Matter
Claim 9 was searched but not rejected under 35 USC § 102 and § 103.
Claim 9 would be allowable if rewritten to overcome the rejection(s) under 35 U.S.C. 101 set forth in this Office action and to include all of the limitations of the base claim and any intervening claims.
The following is a statement of reasons for the indication of allowable subject matter:
The references of record alone or in combination do not disclose or suggest the limitations found within claim 9 limitations as a whole with regards to technical features recited by the claim limitations directed to: “wherein the output matrix is calculated as:
PNG
media_image1.png
33
147
media_image1.png
Greyscale
wherein 0 denotes element-wise division, 1 denotes an all-ones vector, H denotes the factorized matrix, HT denotes the transpose of the factorized matrix, HTV denotes the intermediate matrix.”
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1-20 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more.
In regards to claim 1,
Step 1: This part of the eligibility analysis evaluates whether the claim(s) falls within any statutory category. See MPEP 2106.03:
The claim directs to a statutory category – process.
Step 2A – Prong 1: Judicial Exception Recited?
MPEP 2106.04(a)(2)(II) “The mathematical concepts grouping is defined as mathematical relationships, mathematical formulas or equations, and mathematical calculations.”
Further, the MPEP recites “It is important to note that a mathematical concept need not be expressed in mathematical symbols, because "[w]ords used in a claim operating on data to solve a problem can serve the same purpose as a formula." In re Grams, 888 F.2d 835, 837 and n.1, 12 USPQ2d 1824, 1826 and n.1 (Fed. Cir. 1989). See, e.g., SAP America, Inc. v. InvestPic, LLC, 898 F.3d 1161, 1163, 127 USPQ2d 1597, 1599 (Fed. Cir. 2018) (holding that claims to a ‘‘series of mathematical calculations based on selected information’’ are directed to abstract ideas); Digitech Image Techs., LLC v. Elecs. for Imaging, Inc., 758 F.3d 1344, 1350, 111 USPQ2d 1717, 1721 (Fed. Cir. 2014) (holding that claims to a ‘‘process of organizing information through mathematical correlations’’ are directed to an abstract idea); and Bancorp Servs., LLC v. Sun Life Assurance Co. of Can. (U.S.), 687 F.3d 1266, 1280, 103 USPQ2d 1425, 1434 (Fed. Cir. 2012) (identifying the concept of ‘‘managing a stable value protected life insurance policy by performing calculations and manipulating the results’’ as an abstract idea).”
Yes, the claim recites a mathematical concept, specifically:
projecting an input matrix corresponding to an input sequence comprising feature vectors, according to first learnable weights, into a query matrix (Q) comprising query vectors; projecting the input matrix, according to second learnable weights, into a value matrix (V) comprising value vectors;
These limitations encompass mathematical calculations that involves matrix multiplication the input matrix and weight matrices.
generating a factorized matrix (H) by an incomplete Cholesky factorization according to the query matrix (Q) and a transpose (QT) of the query matrix, wherein dimensions of the factorized matrix are smaller than dimensions of the query matrix;
This limitation encompasses generating a matrix from mathematical calculations (incomplete Cholesky factorization) according to given matrices.
calculating an intermediate matrix (HTV) according to a product between a transpose (HT) of the factorized matrix and the value matrix (V);
and calculating an output matrix according to a product between the factorized matrix and the intermediate matrix.
These limitations involves calculating matrices from products of respective matrices.
Therefore, the claim recites a mathematical concept.
Step 2A – Prong 2: Integrated into a Practical Solution?
MPEP 2106.05(f) Mere Instructions To Apply An Exception has found simply adding a general purpose computer or computer components after the fact to an abstract idea (e.g., a fundamental economic practice or mathematical equation) does not integrate a judicial exception into a practical application or provide significantly more. The following steps are mere instructions to apply:
A computing method, suitable for a transformer model, the computing method comprising (generic computer to apply the abstract idea)
The additional elements have been considered both individually and as an ordered combination in to determine whether they integrate the exception into a practical application. Therefore, no meaningful limits are imposed on practicing the abstract idea.
The claim is directed to the abstract idea.
Step 2B: Claim provides an Inventive Concept?
No, as discussed with respect to Step 2A, the additional limitation is Mere Instructions To Apply An Exception and a generic device does not impose any meaningful limits on practicing the abstract idea and therefore the claim does not provide an inventive concept in Step 2B.
The full context of the claim encompasses utilizing a generic computer to calculate a series of mathematical calculations wherein the transformer model is not trained nor updated.
The additional elements have been considered both individually and as an ordered
combination in the significantly more consideration.
The claim is ineligible.
In regards to claim 2,
Step 1: This part of the eligibility analysis evaluates whether the claim(s) falls within any statutory category. See MPEP 2106.03:
The claim directs to a statutory category – process.
Step 2A Prong 1: The claim recites the following abstract ideas:
The abstract idea(s) in the parent claim(s).
wherein dimensions of the input matrix are n x d, n is a sequence length of the input sequence, and d is a dimension value of the feature vectors in the input sequence.
This limitation directs to a mathematical relationship and encompasses the dimensions of the matrices in relation to variables. See MPEP 2106.04(a)(2)(I)(A.) “A mathematical relationship may be expressed in words or using mathematical symbols. For example, pressure (p) can be described as the ratio between the magnitude of the normal force (F) and area of the surface on contact (A), or it can be set forth in the form of an equation such as p = F/A.”
Step 2A Prong 2: The claim recites the following additional elements which, considered individually and as an ordered combination, do not integrate the abstract idea into a practical application:
The additional element(s) in the parent claim(s).
Step 2B: The claim recites the following additional elements which, considered individually and as an ordered combination, do not amount to significantly more than the abstract idea:
The additional element(s) in the parent claim(s).
In regards to claim 3,
Step 1: This part of the eligibility analysis evaluates whether the claim(s) falls within any statutory category. See MPEP 2106.03:
The claim directs to a statutory category – process.
Step 2A Prong 1: The claim recites the following abstract ideas:
The abstract idea(s) in the parent claim(s).
wherein the incomplete Cholesky factorization is configured to make a product between the factorized matrix and the transpose of the factorized matrix approximate to an exponential function of a shared-QK attention matrix (QQT),
This limitation directs to a mathematical calculation and encompasses calculating the product between matrices. See MPEP 2106.04(a)(2)(I)(C.)
the dimensions of the query matrix (Q) are n x d, the dimensions of the factorized matrix (H) are n x p, p is a parameter corresponding to an iteration count in the incomplete Cholesky factorization
This limitation directs to a mathematical relationship and encompasses the dimensions of the matrices in relation to variables. See MPEP 2106.04(a)(2)(I)(A.) “A mathematical relationship may be expressed in words or using mathematical symbols. For example, pressure (p) can be described as the ratio between the magnitude of the normal force (F) and area of the surface on contact (A), or it can be set forth in the form of an equation such as p = F/A.”
Step 2A Prong 2: The claim recites the following additional elements which, considered individually and as an ordered combination, do not integrate the abstract idea into a practical application:
The additional element(s) in the parent claim(s).
the factorized matrix (H) and the transpose (HT) of the factorized matrix are utilized by the transformer model to replace the shared-QK attention matrix while calculating the output matrix
This limitation directs to merely applying (or equivalent) an abstract idea, or implementing an abstract idea on a computer, or using a computer as a tool to perform an abstract idea wherein the “transformer model” is merely used to apply the abstract idea of calculating the output matrix. See MPEP 2106.05(f)
Step 2B: The claim recites the following additional elements which, considered individually and as an ordered combination, do not amount to significantly more than the abstract idea:
The additional element(s) in the parent claim(s).
the factorized matrix (H) and the transpose (HT) of the factorized matrix are utilized by the transformer model to replace the shared-QK attention matrix while calculating the output matrix
This limitation directs to merely applying (or equivalent) an abstract idea, or implementing an abstract idea on a computer, or using a computer as a tool to perform an abstract idea wherein the “transformer model” is merely used to apply the abstract idea of calculating the output matrix. See MPEP 2106.05(f)
In regards to claim 4,
Step 1: This part of the eligibility analysis evaluates whether the claim(s) falls within any statutory category. See MPEP 2106.03:
The claim directs to a statutory category – process.
Step 2A Prong 1: The claim recites the following abstract ideas:
The abstract idea(s) in the parent claim(s).
wherein the parameter p is utilized by the incomplete Cholesky factorization for approximation
This limitation directs to a mathematical relationship and encompasses the parameter p in relation to the incomplete Cholesky factorization. See MPEP 2106.04(a)(2)(I)(A.) “A mathematical relationship may be expressed in words or using mathematical symbols. For example, pressure (p) can be described as the ratio between the magnitude of the normal force (F) and area of the surface on contact (A), or it can be set forth in the form of an equation such as p = F/A.”
Step 2A Prong 2: The claim recites the following additional elements which, considered individually and as an ordered combination, do not integrate the abstract idea into a practical application:
The additional element(s) in the parent claim(s).
Step 2B: The claim recites the following additional elements which, considered individually and as an ordered combination, do not amount to significantly more than the abstract idea:
The additional element(s) in the parent claim(s).
In regards to claim 5,
Step 1: This part of the eligibility analysis evaluates whether the claim(s) falls within any statutory category. See MPEP 2106.03:
The claim directs to a statutory category – process.
Step 2A Prong 1: The claim recites the following abstract ideas:
The abstract idea(s) in the parent claim(s).
wherein the parameter p is set to be equal to or smaller than d.
This limitation directs to a mathematical relationship and encompasses the parameter p in relation to parameter d. See MPEP 2106.04(a)(2)(I)(A.) “A mathematical relationship may be expressed in words or using mathematical symbols. For example, pressure (p) can be described as the ratio between the magnitude of the normal force (F) and area of the surface on contact (A), or it can be set forth in the form of an equation such as p = F/A.”
Step 2A Prong 2: The claim recites the following additional elements which, considered individually and as an ordered combination, do not integrate the abstract idea into a practical application:
The additional element(s) in the parent claim(s).
Step 2B: The claim recites the following additional elements which, considered individually and as an ordered combination, do not amount to significantly more than the abstract idea:
The additional element(s) in the parent claim(s).
In regards to claim 6,
Step 1: This part of the eligibility analysis evaluates whether the claim(s) falls within any statutory category. See MPEP 2106.03:
The claim directs to a statutory category – process.
Step 2A Prong 1: The claim recites the following abstract ideas:
The abstract idea(s) in the parent claim(s).
wherein the parameter p is set to be equal to or smaller than a rank of the shared-QK attention matrix (QQT)
This limitation directs to a mathematical relationship and encompasses the parameter p in relation to a rank of the QQT matrix. See MPEP 2106.04(a)(2)(I)(A.) “A mathematical relationship may be expressed in words or using mathematical symbols. For example, pressure (p) can be described as the ratio between the magnitude of the normal force (F) and area of the surface on contact (A), or it can be set forth in the form of an equation such as p = F/A.”
Step 2A Prong 2: The claim recites the following additional elements which, considered individually and as an ordered combination, do not integrate the abstract idea into a practical application:
The additional element(s) in the parent claim(s).
Step 2B: The claim recites the following additional elements which, considered individually and as an ordered combination, do not amount to significantly more than the abstract idea:
The additional element(s) in the parent claim(s).
In regards to claim 7,
Step 1: This part of the eligibility analysis evaluates whether the claim(s) falls within any statutory category. See MPEP 2106.03:
The claim directs to a statutory category – process.
Step 2A Prong 1: The claim recites the following abstract ideas:
The abstract idea(s) in the parent claim(s).
wherein the shared-QK attention matrix (QQT) is defined according to a product between the query matrix (Q) and a transpose of the query matrix (QT)
This limitation directs to a mathematical calculation and encompasses calculating a product between two matrices. See MPEP 2106.04(a)(2)(I)(C.)
dimensions of the intermediate matrix (HTV) are smaller than dimensions of the shared-QK attention matrix (QQT)
This limitation directs to a mathematical relationship and encompasses the dimensions of matrix HTV in relation to the dimensions of matrix QQT. See MPEP 2106.04(a)(2)(I)(A.) “A mathematical relationship may be expressed in words or using mathematical symbols. For example, pressure (p) can be described as the ratio between the magnitude of the normal force (F) and area of the surface on contact (A), or it can be set forth in the form of an equation such as p = F/A.”
Step 2A Prong 2: The claim recites the following additional elements which, considered individually and as an ordered combination, do not integrate the abstract idea into a practical application:
The additional element(s) in the parent claim(s).
Step 2B: The claim recites the following additional elements which, considered individually and as an ordered combination, do not amount to significantly more than the abstract idea:
The additional element(s) in the parent claim(s).
In regards to claim 8,
Step 1: This part of the eligibility analysis evaluates whether the claim(s) falls within any statutory category. See MPEP 2106.03:
The claim directs to a statutory category – process.
Step 2A Prong 1: The claim recites the following abstract ideas:
The abstract idea(s) in the parent claim(s).
wherein dimensions of the transpose (QT) of the query matrix are d x n, dimensions of the shared-QK attention matrix (QQT) are n x n, the dimensions of the intermediate matrix (HTV) are p x d
This limitation directs to a mathematical relationship and encompasses the dimensions of each recited respective matrix in relation to the recited variables. See MPEP 2106.04(a)(2)(I)(A.) “A mathematical relationship may be expressed in words or using mathematical symbols. For example, pressure (p) can be described as the ratio between the magnitude of the normal force (F) and area of the surface on contact (A), or it can be set forth in the form of an equation such as p = F/A.”
Step 2A Prong 2: The claim recites the following additional elements which, considered individually and as an ordered combination, do not integrate the abstract idea into a practical application:
The additional element(s) in the parent claim(s).
Step 2B: The claim recites the following additional elements which, considered individually and as an ordered combination, do not amount to significantly more than the abstract idea:
The additional element(s) in the parent claim(s).
In regards to claim 9,
Step 1: This part of the eligibility analysis evaluates whether the claim(s) falls within any statutory category. See MPEP 2106.03:
The claim directs to a statutory category – process.
Step 2A Prong 1: The claim recites the following abstract ideas:
The abstract idea(s) in the parent claim(s).
wherein the output matrix is calculated as: H(HTV) 0 H(H 1) wherein 0 denotes element-wise division, 1 denotes an all-ones vector, H denotes the factorized matrix, HT denotes the transpose of the factorized matrix, HTV denotes the intermediate matrix
This limitation directs to a mathematical calculation and encompasses element-wise division. See MPEP 2106.04(a)(2)(I)(C.)
Step 2A Prong 2: The claim recites the following additional elements which, considered individually and as an ordered combination, do not integrate the abstract idea into a practical application:
The additional element(s) in the parent claim(s).
Step 2B: The claim recites the following additional elements which, considered individually and as an ordered combination, do not amount to significantly more than the abstract idea:
The additional element(s) in the parent claim(s).
In regards to claim 10,
Step 1: This part of the eligibility analysis evaluates whether the claim(s) falls within any statutory category. See MPEP 2106.03:
The claim directs to a statutory category – process.
Step 2A Prong 1: The claim recites the following abstract ideas:
The abstract idea(s) in the parent claim(s).
generating an output sequence by a fully connected layer according to the output matrix
This limitation directs to a mathematical calculation and encompasses matrix multiplication of the output matrix. See MPEP 2106.04(a)(2)(I)(C.)
Step 2A Prong 2: The claim recites the following additional elements which, considered individually and as an ordered combination, do not integrate the abstract idea into a practical application:
The additional element(s) in the parent claim(s).
Step 2B: The claim recites the following additional elements which, considered individually and as an ordered combination, do not amount to significantly more than the abstract idea:
The additional element(s) in the parent claim(s).
In regards to claim 11,
Step 1: This part of the eligibility analysis evaluates whether the claim(s) falls within any statutory category. See MPEP 2106.03:
The claim directs to a statutory category – process.
Step 2A Prong 1: The claim recites the following abstract ideas:
The abstract idea(s) in the parent claim(s).
Step 2A Prong 2: The claim recites the following additional elements which, considered individually and as an ordered combination, do not integrate the abstract idea into a practical application:
The additional element(s) in the parent claim(s).
wherein the input sequence comprises characters or words in a first language, the output sequence comprises characters or words in a second language, the transformer model is configured to translate the input sequence into the output sequence
This limitation merely indicates a field of use or technological environment in which the judicial exception is performed. This type of limitation merely confines the use of the abstract idea to a particular technological environment (natural language translation) and thus fails to add an inventive concept to the claims. See MPEP § 2106.05(h)
Step 2B: The claim recites the following additional elements which, considered individually and as an ordered combination, do not amount to significantly more than the abstract idea:
The additional element(s) in the parent claim(s).
wherein the input sequence comprises characters or words in a first language, the output sequence comprises characters or words in a second language, the transformer model is configured to translate the input sequence into the output sequence
This limitation merely indicates a field of use or technological environment in which the judicial exception is performed. This type of limitation merely confines the use of the abstract idea to a particular technological environment (natural language translation) and thus fails to add an inventive concept to the claims. See MPEP § 2106.05(h)
In regards to claim 12,
Step 1: This part of the eligibility analysis evaluates whether the claim(s) falls within any statutory category. See MPEP 2106.03:
The claim directs to a statutory category – process.
Step 2A Prong 1: The claim recites the following abstract ideas:
The abstract idea(s) in the parent claim(s).
extract, identify or generate the output sequence from the input sequence
This limitation directs to a mental process that can be performed in the human mind, by a human using pen and paper, or using a computer as a tool to perform the concept wherein a person of ordinary skills in the art would be able to read the given words and provide an opinion of a summary. See MPEP 2106.04(a)(2)(III)
Step 2A Prong 2: The claim recites the following additional elements which, considered individually and as an ordered combination, do not integrate the abstract idea into a practical application:
The additional element(s) in the parent claim(s).
the transformer model is configured to…
This limitation directs to merely applying (or equivalent) an abstract idea, or implementing an abstract idea on a computer, or using a computer as a tool to perform an abstract idea. See MPEP 2106.05(f)
wherein each of the input sequence and the output sequence comprises characters or words, the input sequence comprises an article or a document, the output sequence comprises a summary, a classification result, an answer to a question or a title corresponding to the input sequence
This limitation merely indicates a field of use or technological environment in which the judicial exception is performed. This type of limitation merely confines the use of the abstract idea to a particular technological environment (article/document analysis) and thus fails to add an inventive concept to the claims. See MPEP § 2106.05(h)
Step 2B: The claim recites the following additional elements which, considered individually and as an ordered combination, do not amount to significantly more than the abstract idea:
The additional element(s) in the parent claim(s).
the transformer model is configured to…
This limitation directs to merely applying (or equivalent) an abstract idea, or implementing an abstract idea on a computer, or using a computer as a tool to perform an abstract idea. See MPEP 2106.05(f)
wherein each of the input sequence and the output sequence comprises characters or words, the input sequence comprises an article or a document, the output sequence comprises a summary, a classification result, an answer to a question or a title corresponding to the input sequence
This limitation merely indicates a field of use or technological environment in which the judicial exception is performed. This type of limitation merely confines the use of the abstract idea to a particular technological environment (article/document analysis) and thus fails to add an inventive concept to the claims. See MPEP § 2106.05(h)
Claim 13 (machine) is rejected on the same grounds under 35 U.S.C. 101 as claim 1 as they are substantially similar, respectively, Mutatis mutandis.
Claim 14 (machine) is rejected on the same grounds under 35 U.S.C. 101 as claim 2 as they are substantially similar, respectively, Mutatis mutandis.
Claim 15 (machine) is rejected on the same grounds under 35 U.S.C. 101 as claim 3 as they are substantially similar, respectively, Mutatis mutandis.
Claim 16 (machine) is rejected on the same grounds under 35 U.S.C. 101 as claim 7 as they are substantially similar, respectively, Mutatis mutandis.
Claim 17 (machine) is rejected on the same grounds under 35 U.S.C. 101 as claim 8 as they are substantially similar, respectively, Mutatis mutandis.
Claim 18 (machine) is rejected on the same grounds under 35 U.S.C. 101 as claim 10 as they are substantially similar, respectively, Mutatis mutandis.
Claim 19 (machine) is rejected on the same grounds under 35 U.S.C. 101 as claim 11 as they are substantially similar, respectively, Mutatis mutandis.
Claim 20 (machine) is rejected on the same grounds under 35 U.S.C. 101 as claim 12 as they are substantially similar, respectively, Mutatis mutandis.
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
The factual inquiries for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
Claim(s) 1-8 and 13-17 are rejected under 35 U.S.C. 103 as being unpatentable over Kitaev, Nikita, Łukasz Kaiser, and Anselm Levskaya. "Reformer: The efficient transformer." arXiv preprint arXiv:2001.04451 (2020). (“Kitaev”) in view of Zhu, Kaihua, et al. "Parallelizing support vector machines on distributed computers." Advances in neural information processing systems 20 (2011). (“Zhu”) in further view of Wang et al. “Linformer: Self-Attention with Linear Complexity” (2020) (“Wang”).
In regards to claim 1 and analogous claim 13,
Kitaev teaches A computing method, suitable for a transformer model, the computing method comprising: projecting an input matrix corresponding to an input sequence comprising feature vectors, according to first learnable weights, into a query matrix (Q) comprising query vectors;
projecting the input matrix, according to second learnable weights, into a value matrix (V) comprising value vectors;
(Kitaev, Section 1., “Approximate attention computation based on locality-sensitive hashing replaces the O(L2) factor in attention layers with O(LlogL) and so allows operating on long sequences.”)
(Kitaev, Section 2., “The input consists of queries and keys of dimension dk [an input sequence comprising feature vectors], and values of dimension dv. The dot products of the query with all keys are computed, scaled by √dk, and a softmax function is applied to obtain the weights [according to first learnable weights… according to second learnable weights] on the values…
Where do Q, K, V come from? The multi-head attention described above operates on keys, queries and values, but usually we are only given a single tensor of activations A of the shape [batch size, length, dmodel]– e.g., coming from embedding the tokens in a sentence into vectors. To build Q, K and V from A, the Transformer uses 3 different linear layers projecting A into Q, K and V with different parameters. For models with LSH attention, we want queries and keys (Q and K) to be identical [projecting the input matrix… into a query matrix (Q) comprising query vectors/ into a value matrix (V) comprising value vectors; wherein matrices Q and K are identical]. This is easily achieved by using the same linear layer to go from A to Q and K, and a separate one for V. We call a model that behaves like this a shared-QK Transformer.”)
Kitaev teaches calculating an intermediate matrix (HTV) according to a product between a transpose (HT) of the factorized matrix and the value matrix (V);
(Kitaev, Section 2., “The attention can indeed be computed for each query qi separately, only calculating softmax(qiKT √ dk )V [calculating an intermediate matrix (HTV) according to a product between a transpose (HT) of the factorized matrix and the value matrix (V); recall matrices Q and K are identical and the factorized matrix is provided by applying the ICF methods of Zhu to matrix K] once in memory, and then re-computing it on the backward pass when needed for gradients.”)
Kitaev teaches and calculating an output matrix according to a product between the factorized matrix and the intermediate matrix.
(Kitaev, Section 2., “Assuming the keys and values are also packed together into matrices K and V , the matrix of outputs is defined as [calculating an output matrix according to a product between the factorized matrix and the intermediate matrix]:
PNG
media_image2.png
140
792
media_image2.png
Greyscale
”)
However, Kitaev does not explicitly teach generating a factorized matrix (H) by an incomplete Cholesky factorization according to the query matrix (Q) and a transpose (QT) of the query matrix, wherein dimensions of the factorized matrix are smaller than dimensions of the query matrix; calculating an intermediate matrix (HTV) according to a product between a transpose (HT) of the factorized matrix and the value matrix (V);
Zhu teaches generating a factorized matrix (H) by an incomplete Cholesky factorization [according to the query matrix (Q) and a transpose (QT) of the query matrix], wherein dimensions of the factorized matrix are smaller than dimensions of the query matrix;
(Zhu. Section 2.1, “ICF can approximate Q (Q ∈ Rn×n) by a smaller matrix H (H ∈ Rn×p,p n), i.e., Q ≈ HHT [generating a factorized matrix (H) by an incomplete Cholesky factorization… wherein dimensions of the factorized matrix are smaller than dimensions of the query matrix; wherein the ICF methods of Zhu is applied to matrix K of Kitaev wherein matrices K and Q are identical]. ICF, together with SMW (the Sherman-Morrison-Woodbury formula), can greatly reduce the computational complexity in solving an n × n linear system.”)
However, Zhu does not explicitly teach according to the query matrix (Q) and a transpose (QT) of the query matrix
Wang teaches [generating a factorized matrix (H) by an incomplete Cholesky factorization] according to the query matrix (Q) and a transpose (QT) of the query matrix,(Wang, Section I., “In this work, we introduce a novel approach for tackling the self-attention bottleneck in Transformers. Our approach is inspired by the key observation that self-attention is low rank. More precisely, we show both theoretically and empirically that the stochastic matrix formed by self-attention can be approximated by a low-rank matrix [according to the query matrix (Q) and a transpose (QT) of the query matrix; wherein Examiner notes that ICF of Zhu provides a low rank approximation of a matrix and Wang considers self-attention of transformers in terms of low rank factorization]. Empowered by this observation, we introduce a novel mechanism that reduces self-attention to an O(n) operation in both space- and time-complexity: we decompose the original scaled dot-product attention into multiple smaller attentions through linear projections, such that the combination of these operations forms a low-rank factorization of the original attention.”)
Kitaev is considered to be analogous to the claimed invention because they are in the same field of improving transformers. Zhu is considered to be analogous to the claimed invention because they are reasonably pertinent to the problem the inventor faced of reducing memory use and computational time for machine learning through matrix factorization. Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified Kitaev to incorporate the teachings of Zhu in order to provide Incomplete Cholesky Factorization as a low rank matrix factorization method to the matrices of Kitaev as doing so greatly reduces computational complexity in solving an n x n linear system (Zhu, Section 2.1, “ICF, together with SMW (the Sherman-Morrison-Woodbury formula), can greatly reduce the computational complexity in solving an n × n linear system.”)
Kitaev is considered to be analogous to the claimed invention because they are in the same field of improving transformers. Wang is analogous to the claimed invention because they are in the same field of improving transformers with low rank matrix factorization. Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified Kitaev to incorporate the teachings of Wang in order to provide a low rank matrix factorization method to the matrices of Kitaev as doing so reduces overall self-attention complexity and provides greater memory and time efficiency (Wang, Abstract, “In this paper, we demonstrate that the self-attention mechanism can be approximated by a low-rank matrix. We further exploit this finding to propose a new self-attention mechanism, which reduces the overall self-attention complexity from O(n2) to O(n) in both time and space. The resulting linear transformer, the Linformer, performs on par with standard Transformer models, while being much more memory- and time-efficient.”)
Thus, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified Kitaev to incorporate the teachings of Zhu and Wang in order to provide Incomplete Cholesky Factorization (Zhu) as a low rank matrix factorization method (Wang) to the matrices of Kitaev as doing so greatly reduces computational complexity in solving an n x n linear system and reduces overall self-attention complexity.
In regards to claim 2 and analogous claim 14,
Kitaev in view of Zhu and Wang teaches The computing method of claim 1,
Kitaev teaches wherein dimensions of the input matrix are n x d, n is a sequence length of the input sequence, and d is a dimension value of the feature vectors in the input sequence.
(Kitaev, Section 2., “The multi-head attention described above operates on keys, queries and values, but usually we are only given a single tensor of activations A of the shape [batch size, length, dmodel] [wherein dimensions of the input matrix are n x d, n is a sequence length of the input sequence ie length, and d is a dimension value of the feature vectors in the input sequence ie dmodel ]– e.g., coming from embedding the tokens in a sentence into vectors.”)
In regards to claim 3 and analogous claim 15,
Kitaev in view of Zhu and Wang teaches The computing method of claim 2,
Kitaev teaches wherein the incomplete Cholesky factorization is configured to make a product between the factorized matrix and the transpose of the factorized matrix approximate to an exponential function of a shared-QK attention matrix (QQT),
Examiner’s note: Examiner interprets the limitation in light of para. [0043] of the specification wherein KT is replaced with QT (“
PNG
media_image3.png
160
599
media_image3.png
Greyscale
”)
(Kitaev, Section 2., “In practice, the attention function on a set of queries is computed simultaneously, packed together into a matrix Q. Assuming the keys and values are also packed together into matrices K and V , the matrix of outputs is defined as:
PNG
media_image4.png
63
589
media_image4.png
Greyscale
… To build Q, K and V from A, the Transformer uses 3 different linear layers projecting A into Q, K and V with different parameters. For models with LSH attention, we want queries and keys (Q and K) to be identical. This is easily achieved by using the same linear layer to go from A to Q and K, and a separate one for V. We call a model that behaves like this a shared-QK Transformer [wherein the incomplete Cholesky factorization is configured to make a product between the factorized matrix and the transpose of the factorized matrix approximate to an exponential function (see softmax) of a shared-QK attention matrix (QQT); wherein K and Q are identical and Kitaev calls such a model “a shared-QK Transformer” and the ICF methods of Zhu would be applied to matrices of Kitaev to “make a product between the factorized matrix and the transpose of the factorized matrix”; Examiner interprets the original QKT of Kitaev to be the shared-QK attention matrix wherein K and Q are identical].”)
Kitaev teaches the dimensions of the query matrix (Q) are n x d,
(Kitaev, Section 2., “For the LSH attention, we start with two tensors, Q=K and V of the shape [batch size, length, dmodel] [the dimensions of the query matrix (Q) are n x d; length x dmodel].”)
Zhu teaches the dimensions of the factorized matrix (H) are n x p,
(Zhu, Section 2.1, “ICF can approximate Q (Q ∈ Rn×n) by a smaller matrix H (H ∈ Rn×p,p n) [the dimensions of the factorized matrix (H) are n x p], i.e., Q ≈ HHT.”)
Zhu teaches p is a parameter corresponding to an iteration count in the incomplete Cholesky factorization,
(Zhu, Section 2.1, “Our row-based parallel ICF (PICF) works as follows: Let vector v be the diagonal of Q and suppose the pivots (the largest diagonal values) are {i1,i2,...,ik}, the kth iteration of ICF computes three equations:
PNG
media_image5.png
141
655
media_image5.png
Greyscale
where Jk denotes the complement of {i1,i2,...,ik}. The algorithm iterates until the approximation of Q by HkHT k (measured by trace(Q − HkHT k)) is satisfactory, or the predefined maximum iterations (or say, the desired rank of the ICF matrix) p is reached [p is a parameter corresponding to an iteration count in the incomplete Cholesky factorization].”)
Thus, Kitaev in view of Zhu teaches the factorized matrix (H) and the transpose (HT) of the factorized matrix are utilized by the transformer model to replace the shared-QK attention matrix while calculating the output matrix.
(Kitaev, Section 2., “In practice, the attention function on a set of queries is computed simultaneously, packed together into a matrix Q. Assuming the keys and values are also packed together into matrices K and V , the matrix of outputs is defined as: [the factorized matrix (H) and the transpose (HT) of the factorized matrix are utilized by the transformer model to replace the shared-QK attention matrix while calculating the output matrix; wherein the factorized matrix is determined by applying the ICF methods of Zhu to the matrix of Kitaev]
PNG
media_image4.png
63
589
media_image4.png
Greyscale
”)
In regards to claim 4,
Kitaev in view of Zhu and Wang teaches The computing method of claim 3,
Zhu teaches wherein the parameter p is utilized by the incomplete Cholesky factorization for approximation.
(Zhu, Section 2.1, “ICF can approximate Q (Q ∈ Rn×n) [recall Q would be provided by Kitaev] by a smaller matrix H (H ∈ Rn×p,p n), i.e., Q ≈ HHT.”)
In regards to claim 5,
Kitaev in view of Zhu and Wang teaches The computing method of claim 4,
Zhu teaches wherein the parameter p is set to be equal to or smaller than d.
(Zhu, Section 2.1, “ICF can approximate Q (Q ∈ Rn×n) [recall Q would be provided by Kitaev] by a smaller matrix H (H ∈ Rn×p,p<<n), i.e., Q ≈ HHT.”)
In regards to claim 6,
Kitaev in view of Zhu and Wang teaches The computing method of claim 4,
Zhu teaches wherein the parameter p is set to be equal to or smaller than a rank of the shared-QK attention matrix (QQT)
(Zhu, Section 2.1, “The algorithm iterates until the approximation of Q by HkHT k (measured by trace(Q − HkHT k)) is satisfactory, or the predefined maximum iterations (or say, the desired rank of the ICF matrix [wherein the parameter p is set to be equal to or smaller than a rank of the shared-QK attention matrix (QQT)]) p is reached.”)
In regards to claim 7 and analogous claim 16,
Kitaev in view of Zhu and Wang teaches The computing method of claim 3,
Kitaev teaches wherein the shared-QK attention matrix (QQT) is defined according to a product between the query matrix (Q) and a transpose of the query matrix (QT),
(Kitaev, Section 2., “In practice, the attention function on a set of queries is computed simultaneously, packed together into a matrix Q. Assuming the keys and values are also packed together into matrices K and V , the matrix of outputs is defined as:
PNG
media_image4.png
63
589
media_image4.png
Greyscale
… To build Q, K and V from A, the Transformer uses 3 different linear layers projecting A into Q, K and V with different parameters. For models with LSH attention, we want queries and keys (Q and K) to be identical. This is easily achieved by using the same linear layer to go from A to Q and K, and a separate one for V. We call a model that behaves like this a shared-QK Transformer [wherein the shared-QK attention matrix (QQT) is defined according to a product between the query matrix (Q) and a transpose of the query matrix (QT); wherein matrices K and Q are identical and Examiner notes the original shared-QK attention matrix does not utilize the ICF methods of Zhu].”)
Kitaev teaches dimensions of the intermediate matrix (HTV) are smaller than dimensions of the shared-QK attention matrix (QQT).
(Zhu, Section 2.1, “ICF can approximate Q (Q ∈ Rn×n) by a smaller matrix H (H ∈ Rn×p,p n) [dimensions of the intermediate matrix (HTV) are smaller than dimensions of the shared-QK attention matrix (QQT)], i.e., Q ≈ HHT.”)
In regards to claim 8 and analogous claim 17,
Kitaev in view of Zhu and Wang teaches The computing method of claim 7,
Kitaev teaches wherein dimensions of the transpose (QT) of the query matrix are d x n,
(Kitaev, Section 2., “To calculate the memory use of the attention mechanism, let us focus on the attention computation from Equation 1. Let us assume that Q, K and V all have the shape [batch size,length,dmodel] [wherein dimensions of the transpose (QT) of the query matrix are d x n ie dmodel x length; wherein transposing a matrix switches its rows and columns].”)
Kitaev teaches dimensions of the shared-QK attention matrix (QQT) are n x n,
(Kitaev, Section 2., “The main issue is the term QKT, which has the shape [batch size,length,length] [dimensions of the shared-QK attention matrix (QQT) are n x n; ie length x length].”)
Kitaev in view of Zhu teaches the dimensions of the intermediate matrix (HTV) are p x d.
Zhu teaches the dimensions of the transposed factorized matrix being p x n
(Zhu, Section 2.1, “ICF can approximate Q (Q ∈ Rn×n) by a smaller matrix H (H ∈ Rn×p,p n) [factorized matrix n x p; transposed factorized matrix being p x n], i.e., Q ≈ HHT.”)
Kitaev teaches Value matrix with dimensions n x d
(Kitaev, Section 2., “To calculate the memory use of the attention mechanism, let us
focus on the attention computation from Equation 1. Let us assume that Q, K and V all have
the shape [batch size,length,dmodel] [matrix V being n x d].”)
Thus, the intermediate matrix must have dimensions p x n from multiplying the transposed factorized matrix with the value matrix
(Kitaev, Section 2., “Assuming the keys and values are also packed together into matrices K and V , the matrix of outputs is defined as [the intermediate matrix must have dimensions p x n from multiplying the transposed factorized matrix [p x n] with the value matrix [n x d]]:
PNG
media_image2.png
140
792
media_image2.png
Greyscale
”)
Claim(s) 10-11 and 18-19 are rejected under 35 U.S.C. 103 as being unpatentable over Kitaev in view of Zhu and Wang in further view of Vaswani et al. “Attention Is All You Need” (2017) (“Vaswani”)
In regards to claim 10 and analogous claim 18,
Kitaev in view of Zhu and Wang teaches The computing method of claim 1,
However, Kitaev in view of Zhu and Wang does not explicitly teach further comprising: generating an output sequence by a fully connected layer according to the output matrix
Vaswani teaches further comprising: generating an output sequence by a fully connected layer according to the output matrix.
Vaswani, pg. 5, Section 3.3, Paragraph 1 “In addition to attention sub-layers, each of the layers in our encoder and decoder contains a fully
connected feed-forward network, which is applied to each position separately and identically. This consists of two linear transformations with a ReLU activation in between.
FFN(x) = max(0, xW1 + b1)W2 + b2 (2)”
x is the output matrix from the self-attention layers, and the two linear transformations together are a fully-connected layer that generate the output sequence.
Vaswani considered to be analogous to the claimed invention because they are in the same field of transformers with self-attention. Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified Kitaev in view of Zhu and Wang to incorporate the teachings of Vaswani in order to provide basic architecture components of a transformer as doing so realizes the overall transformer architecture and provides the benefit of successful generalization to English constituency parsing (Vaswani, Abstract, “We propose a new simple network architecture, the Transformer, based solely on attention mechanisms, dispensing with recurrence and convolutions entirely. Experiments on two machine translation tasks show these models to be superior in quality while being more parallelizable and requiring significantly less time to train. Our model achieves 28.4 BLEU on the WMT 2014 English to-German translation task, improving over the existing best results, including ensembles, by over 2 BLEU. On the WMT 2014 English-to-French translation task, our model establishes a new single-model state-of-the-art BLEU score of 41.8 after training for 3.5 days on eight GPUs, a small fraction of the training costs of the best models from the literature. We show that the Transformer generalizes well to other tasks by applying it successfully to English constituency parsing both with large and limited training data.”)
In regards to claim 11 and analogous claim 19,
Kitaev in view of Zhu, Wang and Vaswani teaches The computing method of claim 10,
Vaswani teaches wherein the input sequence comprises characters or words in a first language, the output sequence comprises characters or words in a second language, the transformer model is configured to translate the input sequence into the output sequence.
Vaswani, pg. 2, Section 3, Paragraph 1 “Most competitive neural sequence transduction models have an encoder-decoder structure [5, 2, 35]. Here, the encoder maps an input sequence of symbol representations (x1, ..., xn) to a sequence of continuous representations z = (z1, ..., zn). Given z, the decoder then generates an output sequence (y1, ..., ym) of symbols one element at a time…”
Vaswani, pg. 1, Abstract “…Experiments on two machine translation tasks show these models to be superior in quality while being more parallelizable and requiring significantly less time to train. Our model achieves 28.4 BLEU on the WMT 2014 English-to-German translation task, improving over the existing best results, including ensembles, by over 2 BLEU. On the WMT 2014 English-to-French translation task, our model establishes a new single-model state-of-the-art BLEU score of 41.8…”
Discloses wherein the input sequence comprises characters or words (symbols) in a first language (English), the output sequence comprises characters or words (symbols) in a second language (German/French), the transformer model is configured to translate the input sequence into the output sequence.
Claim(s) 12 and 20 are rejected under 35 U.S.C. 103 as being unpatentable over Kitaev in view of Zhu and Wang in further view of Vaswani in further view of Devlin et al. “BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding" (2019) (“Devlin”)
In regards to claim 12 and analogous claim 20,
Kitaev in view of Zhu, Wang and Vaswani teaches The computing method of claim 10,
However, Kitaev in view of Zhu, Wang and Vaswani does not explicitly teach wherein each of the input sequence and the output sequence comprises characters or words, the input sequence comprises an article or a document, the output sequence comprises a summary, a classification result, an answer to a question or a title corresponding to the input sequence, the transformer model is configured to extract, identify or generate the output sequence from the input sequence.
Devlin teaches wherein each of the input sequence and the output sequence comprises characters or words, the input sequence comprises an article or a document, the output sequence comprises a summary, a classification result, an answer to a question or a title corresponding to the input sequence, the transformer model is configured to extract, identify or generate the output sequence from the input sequence.
Devlin, pg. 4, Column 1, Input/Output Representations, Paragraphs 1-2 “To make BERT handle a variety of down-stream tasks, our input representation is able to unambiguously represent both a single sentence and a pair of sentences (e.g., <Question, Answer>) in one token sequence... We use WordPiece embeddings (Wu et al., 2016) with a 30,000 token vocabulary. The first token of every sequence is always a special classification token ([CLS])...”
Discloses input and output sequences comprising characters or words.
Devlin, pg. 5, Column 1, Pre-training data “For the pre-training corpus we use the BooksCorpus (800M words) (Zhu et al., 2015) and English Wikipedia (2,500M words). For Wikipedia we extract only the text passages and ignore lists, tables, and headers. It is critical to use a document-level corpus rather than a shuffled sentence-level corpus such as the Billion Word Benchmark (Chelba et al., 2013) in order to extract long contiguous sequences.”
Discloses the input sequence comprises a document.
Devlin, pg. 5, Column 2, Paragraph 1 “…At the output, the token representations are fed into an output layer for token-level tasks, such as sequence tagging or question answering, and the [CLS] representation is fed into an output layer for classification, such as entailment or sentiment analysis.”
Discloses the output sequence comprises a classification result or answer to a question corresponding to the input sequence, and that the transformer model is configured to extract/identify the output sequence from the input sequence.
Devlin is considered to be analogous to the claimed invention because they are in the same field of transformers with self-attention for particular NLP tasks. It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to apply the input/output sequences and downstream task heads taught by Devlin to transformer architecture taught by Kitaev in view of Zhu, Wang and Vaswani because it allows for fine-tuning for multiple output tasks without substantial modifications. This would result in a transformer configured to extract, identify, or generate output sequences as claimed with the incorporated efficiency improvements into the transformer’s attention mechanism provided by the combination of Kitaev in view of Zhu, Wang and Vaswani (See Devlin, pg. 1, Abstract, Paragraph 1 “…the pre-trained BERT model can be finetuned with just one additional output layer to create state-of-the-art models for a wide range of tasks, such as question answering and language inference, without substantial task-specific architecture modifications.”)
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
NPL: Fournier, Quentin, Gaétan Marceau Caron, and Daniel Aloise. "A Practical Survey on Faster and Lighter Transformers." arXiv preprint arXiv:2103.14636 (2021).
Any inquiry concerning this communication or earlier communications from the examiner should be directed to JASMINE THAI whose telephone number is (703)756-5904. The examiner can normally be reached M-F 8-4.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Michael Huntley can be reached at (303) 297-4307. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/J.T.T./Examiner, Art Unit 2129
/MICHAEL J HUNTLEY/Supervisory Patent Examiner, Art Unit 2129
Prosecution Insights