{"id":"28baafcd-275b-49a2-80c7-4e215dab4b85","arxiv_id":"2411.17887","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A scan algorithm using only constant-size matrix multiplications achieves O(log_s n) depth and O(n/s^2) matrix multiplications in the TCU model.","lead":"This paper gives a parallel prefix-sum (scan) algorithm for the Tensor Core Unit model of computation, where multiplying constant-size square matrices is the basic operation. It claims logarithmic depth, linear work, and an affirmative answer to whether tensor-core machines can sort efficiently.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The claimed depth bound 2 floor(log_s n) for arbitrary n is not supported: the §2.2 overlap assertion and the bound on |w| both fail for small n, so the exact depth statement is false as stated.","rationale":"The reader's weakest assumption identifies the same load-bearing concern: the overlap of the w-scan with the down-sweep of the largest chunks is asserted without proof or condition. My stress-test confirms and sharpens this concern. The w-size bound in §2.2 is internally inconsistent with the paper's own base-s representation: a number just below s^{k1+1} has k1+1 nonzero digits, not k1, so the scan of w can be one logarithm level larger than claimed. The concrete case s=2, n=31 gives a minimum depth of 10 under the described four-step algorithm, strictly greater than the advertised 2 floor(log_2 31) = 8. This makes the abstract's exact depth claim false as stated, although the asymptotic claim of O(log n) depth and O(n/s^2) matrix multiplications remains plausible after a corrected analysis, e.g. depth 2 floor(log_s n) + O(log log_s n). The paper has real strengths: the power-of-s case is analyzed correctly (Lemma 1, Theorem 1), the recursive correctness proof in Appendix A.1 is sound, and the reference implementation is concrete and reproducible. The conditional verdict is therefore appropriate: the paper should qualify the arbitrary-n depth bound or provide an explicit schedule/proof of the overlap. My read does not change the reader's verdict.","tokens_in":11506,"tokens_out":8393,"duration_ms":75171,"concrete_test":"For s=2 and n=31, instantiate the four-step algorithm: segment sizes are 16, 8, 4, 2, 1; verify that |w| = 5, so w must be zero-padded to length 8, giving a w-scan depth of 5 rounds. Schedule the critical path under the proposed overlap: the size-16 chunk's up-sweep takes rounds 1-4; its down-sweep occupies rounds 5-7; w-scan starts at round 5 but needs 5 rounds, ending at round 9; the broadcast in Step 4 for the chunks after the first must wait until the w-scan completes, so it occurs at round 10. The resulting makespan 10 exceeds the claimed bound 2 floor(log_2 31) = 8. If this schedule is accepted, the advertised exact depth bound is already violated for a concrete small input.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (Abstract; Corollary 1) that depth is at most 2 floor(log_s n) for every n depends on the unproven overlap in §2.2: the scan of the segment-maxima vector w is said to be overlapped with the 2nd phase of the largest chunks. Two concrete problems arise. First, Step 2 bounds |w| by k1(s-1), but for n = s^{k1+1} - 1 the base-s expansion has k1+1 nonzero digits, so |w| = (k1+1)(s-1). For s=2, n=31, |w| = 5, not 4. Second, even with the claimed size, the overlap requires w's scan depth, 2 ceil(log_s |w|) - 1, to fit inside the largest chunk's down-sweep window of k1-1 rounds, but no schedule or quantitative condition is given. In the s=2, n=31 case, w becomes available after 4 up-sweep rounds, its scan needs 5 rounds, and only 3 down-sweep rounds of the size-16 chunk are available for overlap; at least 2 extra rounds remain, and after the subsequent broadcast round the total depth is at least 10, exceeding 2 floor(log_2 31) = 8. Thus the exact bound is not achieved by the described algorithm; the correct general bound is 2 floor(log_s n) + O(log log n), and the abstract's strongest claim is an overclaim.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes MatMulScan, a parallel prefix-sum (scan) algorithm for the (s^2, ℓ)-TCU model, in which multiplication of two constant-size s×s matrices is the basic operation. For inputs of size n = s^k, the paper proves a depth of 2k−1, O(n/s^2) matrix multiplications, and O(n + ℓk) time. It then extends the algorithm to arbitrary n by decomposing n in base s, running Algorithm 1 independently on the resulting segments, scanning the vector w of segment maxima, and broadcasting the scanned values to later segments. The central claims, stated in the Abstract and Corollary 1, are that for every n the algorithm has depth at most 2⌊log_s n⌋, performs O(n/s^2) matrix multiplications, and runs in O(n(1 + ℓ/s^2)/p + (s^2 + ℓ) log_s n) time with p tensor core units.","tokens_in":11741,"tokens_out":27116,"duration_ms":246919,"significance":"If the central claim held, the paper would establish that prefix sums have logarithmic depth in the TCU model, generalize the Brent-Kung scan to a matrix-based setting, and support the claim that TCUs can be used for sorting. The power-of-s part of the analysis is clean and, as far as I can verify, correct: Lemma 1 and Theorem 1 are supported by a straightforward induction and by counting batched matrix multiplications. The paper also provides an end-to-end Python reference implementation and a recursive correctness proof, which are concrete strengths. The arbitrary-length extension in Section 2.2, however, has load-bearing gaps: the size bound on w is inaccurate and the overlap argument that produces the exact depth bound is not proved. The result remains plausible in an asymptotic form, but the advertised exact depth bound for all n is not supported by the described algorithm.","major_comments":[{"comment":"The bound |w| ≤ k1(s−1) is incorrect. For n = s^{k1+1}−1 the base-s expansion has k1+1 nonzero digits, each contributing up to s−1 segments. For example, for s = 3 and n = 26 (k1 = 2), the segments are 9, 9, 3, 3, 1, 1, and five offset values (totals of the first five segments) are needed, so |w| = 5, whereas k1(s−1) = 4. This invalidates the choice of q in Step 3 and consequently the depth calculation based on that q.","section":"Section 2.2, Step 2/3"},{"comment":"The claim that Steps 2 and 3 'can be overlapped with the 2nd phase of the execution of the first step for large enough n' is asserted without a schedule or a quantitative condition. The overlap fails for concrete inputs: for s = 3, n = 26, the largest segments have k1 = 2, so their down-sweep is only one round, while the scan of w (with q = 2, i.e., length 9) needs three rounds. Even with optimistic pipelining, the last broadcast cannot be completed within 2⌊log_3 26⌋ = 4 rounds. Thus Corollary 1's unqualified exact depth bound is not established for arbitrary n. The authors should either provide a precise schedule and a condition on k1 under which the overlap is complete, or weaken the depth claim to 2⌊log_s n⌋ + O(log_s log_s n).","section":"Section 2.2, Depth analysis"}],"minor_comments":[{"comment":"The padding rule should be stated in terms of the actual number of entries in w, not the erroneous bound k1(s−1); after fixing the bound, the text should define q by |w| ≤ s^q.","section":"Section 2.2, Step 3"},{"comment":"The sums over i ≥ 1 use µ_i and k_i without a precise indexing convention for the base-s expansion; please define the digit indices explicitly so the reader can follow the bound on the number of segments.","section":"Section 2.2, decomposition notation"},{"comment":"The claim that the paper 'resolve[s] in the affirmative the open question “can TCU sort?”' is not backed by an explicit sorting theorem or a detailed reduction; consider softening this to a consequence of the scan result or providing a formal corollary.","section":"Section 1, second page"},{"comment":"The execution diagram would be much more convincing if it included a concrete round-by-round schedule for the overlap of the w-scan with the largest segments' down-sweep, together with the quantitative condition on k1.","section":"Figure 3 and Section 2.2"},{"comment":"Reference [1] contains a typo: 'Sythesis' should be 'Synthesis'.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The reader's stress-test note about n = 31 is not the strongest example, because w can be taken to exclude the final singleton and then |w| = 4 for s = 2, n = 31. The s = 3, n = 26 example is cleaner and shows a genuine gap in the arbitrary-n depth claim. This is a fixable problem: the power-of-s case appears sound, and weakening the arbitrary-n depth to 2⌊log_s n⌋ + O(log_s log_s n) preserves the main asymptotic results. I would not reject on this basis, but the abstract and Corollary 1 need to be corrected or the algorithm needs a rigorous schedule."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"I read this paper carefully, and I think the power-of-s part is genuinely good. The idea of encoding the local prefix sum and the scalar-vector add as multiplication by fixed matrices Ls and Bs is clean, and the up/down sweep with batched multiplications is a natural but effective mapping to the (s^2, l)-TCU model. Lemma 1 is correct: depth 2k-1, linear work, O(n + l log n) time. The comparison with [8] is fair and shows a real asymptotic improvement. The reference implementation in the appendix and the recursive correctness proof are useful. The remark that this answers 'can TCU sort?' via radix sort is a nice byproduct.\n\nThe soft spot is Section 2.2. The exact depth bound 2 floor(log_s n) for arbitrary n is not supported. Two concrete problems. First, the size of w is bounded as at most k1(s-1), but for n = s^{k1+1} - 1 the base-s expansion has k1+1 nonzero digits, so |w| can be (k1+1)(s-1). Second, the claim that the scan of w can be overlapped with the second phase of the largest chunks is asserted with no schedule and no quantitative condition. For s=2, n=31, the w-scan needs 5 rounds while the largest chunk's down-sweep window is only 3 rounds; the depth is at least 10, not 8. The correct general bound is 2 floor(log_s n) + O(log log n). This is an overclaim in the abstract and Corollary 1, not a fatal flaw for the asymptotic claim but a real error as stated.\n\nThe work and matrix count for general n look plausible asymptotically, but they inherit some of the same looseness. The paper is honest about practical limitations—sparse TCU utilization, ignored memory costs, no high-performance implementation—which I appreciate.\n\nWho should read it: anyone working on algorithms for tensor-core-style models, or on parallel prefix circuits. The power-of-s result is a solid contribution that stands on its own. The general-n part needs a revision.\n\nRecommendation: send to peer review. The core idea and analysis for the main case are sound, and the general-n issue is fixable. I'd ask the authors to either give a real schedule for the overlap or restate the bound with the additive log log term.","headline":"The power-of-s scan analysis is solid and worth knowing; the arbitrary-n depth bound is overclaimed and should be corrected.","tokens_in":12389,"tokens_out":4338,"would_cite":true,"duration_ms":37505,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Prefix sums—the running totals of a vector—can be computed in logarithmic depth on tensor core units, using only multiplications by two fixed matrices, this paper argues.","keywords":["Prefix Sum","Scan","Matrix Multiplication","Tensor Core Unit Model","Parallel Algorithms","Work-Depth Analysis","Radix Sort"],"falsifier":"Take an input length $n$ that is not a power of $s$ and count the matrix-multiplication rounds of the full procedure: if the chunk-maxima scan cannot be scheduled inside the largest chunk's down-sweep window—for instance at $s=2$, $n=31$—then the measured depth exceeds $2\\lfloor\\log_s(n)\\rfloor$, and the advertised exact bound fails for that $n$.","tokens_in":11167,"feed_emoji":"🧮","tokens_out":13418,"duration_ms":103137,"temperature":0.7,"pith_summary":"This paper claims that prefix sums—the running totals of a vector—can be computed in logarithmic depth on hardware whose basic operation is multiplication of small square matrices, the Tensor Core Unit (TCU) model. The proposed MatMulScan algorithm performs the scan entirely through multiplications by two fixed constant matrices, one that computes local prefix sums and one that adds a broadcast scalar to a vector. For any input of size $n$, the paper argues the depth is at most $2\\lfloor\\log_s(n)\\rfloor$, the number of $s\\times s$ matrix multiplications is $O(n/s^2)$, and with $p$ tensor cores the runtime is $O(n(1+\\ell/s^2)/p + (s^2+\\ell)\\log_s(n))$. The claimed bounds make prefix sums logarithmic-depth in the TCU model and, via the standard reduction, put radix sort on tensor core units.","feed_headline":"Prefix sums run in logarithmic depth on tensor cores","feed_subtitle":"Matrix-multiply scan computes running totals in depth 2 log_s n and puts radix sort on tensor-core hardware.","key_machinery":"The load-bearing objects are two constant $s\\times s$ matrices: $\\mathbf{L}_s$, the lower-triangular all-ones matrix, whose product with a vector is its local prefix sum, and $\\mathbf{B}_s$, the identity matrix with its first column set to all ones, whose product with a vector $[\\alpha;\\mathbf{q}]$ returns $\\mathbf{q}+\\alpha\\mathbf{1}$. The batch procedure reshapes each strided subvector into an $s\\times s$ column-major matrix (zero-padding as needed), multiplies all such matrices by the same constant matrix in a single batched tensor-core call, and flattens the result. The up-sweep uses $\\mathbf{L}_s$ to form prefix sums on exponentially increasing strides; the down-sweep uses $\\mathbf{B}_s$ to add each chunk's correct preceding total. For arbitrary input lengths, the base-$s$ decomposition into chunks of sizes $s^{k_i}$, together with the scan of the vector of chunk maxima, is what keeps the depth logarithmic.","core_discovery":"MatMulScan computes the inclusive prefix sum of an $n$-vector by alternating an up-sweep and a down-sweep. In the up-sweep, entries gathered with stride $s^t$ are multiplied by the lower-triangular all-ones matrix $\\mathbf{L}_s$, giving local prefix sums on chunks of size $s$; in the down-sweep, the matrix $\\mathbf{B}_s$ (the identity with first column all ones) broadcasts and adds the correct preceding total to each local block. For $n=s^k$ the depth is $2\\log_s(n)-1$ and the number of scalar additions is $\\lceil n(1+s/2)\\rceil + O(s^3\\log_s n)$. For arbitrary $n$, the paper writes $n$ in base $s$, runs the power-of-$s$ routine on each chunk, scans the vector of chunk maxima with the same algorithm, and adds the maxima back into the chunks, yielding depth at most $2\\lfloor\\log_s(n)\\rfloor$ and $O(n/s^2)$ matrix multiplications overall. The paper gives a recursive correctness proof in the appendix and presents the result as resolving positively the question 'can TCU sort?', since radix sort reduces to prefix sums.","pith_inferences":["The paper leaves implicit a schedule for the overlap claimed in Section 2.2; until one is given, the exact $2\\lfloor\\log_s(n)\\rfloor$ bound for arbitrary $n$ rests on that scheduling assumption rather than on the code as written.","Because the down-sweep uses $\\mathbf{B}_s$ mainly for a scalar-vector addition, an implementation could route that phase through a nearby vector unit, as the paper itself suggests, to avoid the very low tensor-core utilization of that phase.","The construction is self-similar, so one could recursively apply MatMulScan to the chunk-maximum vector instead of padding it to a power of $s$; a careful overlap analysis might then give an exact logarithmic depth for all $n$.","If tensor cores ever support matrix products over semirings other than ordinary arithmetic, the same $\\mathbf{L}_s$ and $\\mathbf{B}_s$ products would deliver prefix scans for min-plus or boolean associative operators."],"forward_implications":["With $p$ tensor core units, prefix sums of $n$ elements run in $O(n(1+\\ell/s^2)/p + (s^2+\\ell)\\log_s(n))$ time, making the trade-off between matrix size $s$, latency $\\ell$, and parallelism $p$ explicit.","Radix sort is implementable on tensor core units through the standard reduction of sorting to prefix sums, settling the 'can TCU sort?' question in the affirmative.","For $s=4$, the TCU depth is $\\log_2(n)-1$, halving the depth of the $s=2$ case at the price of roughly $3n$ scalar additions rather than $2n$.","The total number of $s\\times s$ matrix multiplications is $O(n/s^2)$, so for fixed $s$ the matrix-multiplication cost is linear in $n$ with a small constant.","Since the paper states the results extend from addition to any associative operator, the same depth and work picture applies to prefix computations under other associative operations."],"supporting_citations":[{"why":"defines the $(s^2,\\ell)$-TCU model used for all depth and time statements and argues tensor units can be used beyond deep learning.","marker":"[7]"},{"why":"introduces the tensor-core model and the open question of whether such units can sort, which the paper answers through its scan result.","marker":"[6]"},{"why":"presents the classic two-phase (up-sweep/down-sweep) scan construction that Algorithm 1 generalizes.","marker":"[3]"},{"why":"reduces radix sort to prefix sums, the connection the paper uses to claim sorting on tensor cores.","marker":"[1]"},{"why":"provides the parallel-evaluation theorem that converts depth and work into a runtime bound for $p$ processors.","marker":"[4]"},{"why":"supplies the textbook base-$s$ decomposition for arbitrary input lengths that Section 2.2 adapts.","marker":"[12]"}],"fun_headline_variants":["Tensor-core scan hits log-depth with matrix multiplies","MatMulScan: prefix sums in log_s n depth","Scan via matmul: log-depth prefix sums on TCUs","Matrix multiplication gives log-depth scan for TCUs","TCU scan in log depth: matmul does it"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The exact $2\\lfloor\\log_s(n)\\rfloor$ depth bound for arbitrary $n$ depends on the assertion that the scan of the vector of per-chunk maximum values can be fully overlapped with the down-sweep of the largest chunks, an overlap the paper states for 'large enough $n$' without giving a size condition or schedule.","fun_headline_variants_meta":{"raw":{"variants":["Tensor-core scan hits log-depth with matrix multiplies","MatMulScan: prefix sums in log_s n depth","Scan via matmul: log-depth prefix sums on TCUs","Matrix multiplication gives log-depth scan for TCUs","TCU scan in log depth: matmul does it"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000568,"raw_usage":{"total_tokens":2679,"prompt_tokens":927,"completion_tokens":1752,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":543,"completion_tokens_details":{"reasoning_tokens":1683}},"tokens_in":543,"tokens_out":1752,"duration_ms":11952,"temperature":1.0,"reasoning_tokens":1683,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T11:45:53.856853+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take an input length $n$ that is not a power of $s$ and count the matrix-multiplication rounds of the full procedure: if the chunk-maxima scan cannot be scheduled inside the largest chunk's down-sweep window—for instance at $s=2$, $n=31$—then the measured depth exceeds $2\\lfloor\\log_s(n)\\rfloor$, and the advertised exact bound fails for that $n$.","supporting_citations":[{"cited_title":"In: International Conference on Parallel and Distributed Computing (Euro-Par)","cited_arxiv_id":null,"evidence_quote":"defines the $(s^2,\\ell)$-TCU model used for all depth and time statements and argues tensor units can be used beyond deep learning."},{"cited_title":"In: Proceedings of the Symposium on Theory of Computing (STOC)","cited_arxiv_id":null,"evidence_quote":"presents the classic two-phase (up-sweep/down-sweep) scan construction that Algorithm 1 generalizes."},{"cited_title":"In: Sythesis of parallel algo- rithms, pp","cited_arxiv_id":null,"evidence_quote":"reduces radix sort to prefix sums, the connection the paper uses to claim sorting on tensor cores."},{"cited_title":"Morgan Kaufmann, fourth edn","cited_arxiv_id":null,"evidence_quote":"supplies the textbook base-$s$ decomposition for arbitrary input lengths that Section 2.2 adapts."}],"review_version":1}