{"id":"4ff210dd-163f-4b29-8e81-64044f55bc3d","arxiv_id":"2506.06041","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"A corner-tree algorithm computes a large class of two-parameter iterated sums in linear time, enabling a cheap tensor-to-tensor neural layer that matches larger ResNets on CIFAR and works for texture anomaly detection.","lead":"The paper introduces a new image-processing layer, called FIS, that computes a type of iterated-sum feature in time that grows linearly with the number of pixels. It reports that swapping some ResNet layers for FIS matches a larger ResNet's accuracy with far fewer parameters, and shows strong anomaly detection on texture images.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The O(n T1 T2) claim is plausible only if each cumsum pass is a fixed number of prefix/infix scans; the stated complexity is not proven for arbitrary corner-tree depth because Eq. (4) nests per-edge cumulative scans whose cost per node is not normalized in the text.","rationale":"The reader's verdict targeted expressiveness, a useful but secondary concern. The paper's central claim is the linear-time algorithm, and that is where the scientific risk is highest. I read Section 3.2 carefully: Eq. (4) defines CTPS for a tree by pointwise multiplying the root's function with per-child cumsum outputs, each of which is itself a recursive CTPS. The complexity argument is stated in one sentence and refers to code instead of a proof. The known algorithmic result (Even-Zohar and Leng corner trees) is for permutation-counting in linear time, but the transfer to two-parameter image tensors with eight directional predicates is not automatic; the runtime depends on whether cumsum for arbitrary directions can be reduced to a constant number of prefix passes along each axis, which is not shown. If each direction requires its own scan per node, the bound becomes O(n^2 T1 T2). The experiment in Section 6.1.6 uses short training runs and cannot distinguish a 2x or 3x constant factor from a superlinear term, so the claimed complexity remains unverified. I therefore keep the CONDITIONAL verdict rather than moving to ACCEPT or REJECT, but my concrete test, if it passes, would resolve the concern and likely allow acceptance.","tokens_in":19574,"tokens_out":1661,"duration_ms":16106,"concrete_test":"Instrument the released repo to count, for each corner-tree vertex, the number of full-grid prefix-sum passes performed by its cumsum calls while processing a 32x32 input with a depth-8 linear tree and a depth-8 random tree. If the total number of passes is proportional to n (as Eq. 4 claims), the O(n T1 T2) bound holds; if it is proportional to the number of edges per level summed over levels, the effective complexity is superlinear and the headline complexity claim needs revision.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The paper's flagship complexity claim (Section 3.2) is that corner-tree sums are computable in O(n T1 T2) time and space via Eq. (4), where each edge calls cumsum over one of eight directional predicates. That bound is clean if every cumsum pass is a constant number of prefix/infix scans over the T1-by-T2 grid. But the paper never defines the cost model for cumsum: for a fixed direction, e.g. NE(t,r), the sum in Eq. (5) is over a quadrant, and a naive per-pixel quadrant accumulation is O(T1 T2) per child per node, which would give O(n T1 T2) per level, hence O(n^2 T1 T2) in total. The text asserts 'linear time and space' and refers to an annotated implementation rather than pseudocode, so there is no verifiable proof that the recursive scan structure really matches the claimed bound. The corner tree can be of depth n/2 (e.g. the linear/NE trees used in experiments), and the recursion in Eq. (4) multiplies child CTPS values pointwise before the parent's cumsum. If each level requires its own full-grid scan, the claimed total complexity fails. This is not an expressiveness objection—it is a gap in the central algorithmic proof. A concrete check: implement a depth-8 linear corner tree on a 32x32 grid, instrument the number of grid-level scans, and measure wall-time versus n T1 T2; if scans grow as n^2, the complexity claim in Section 3.2 should be corrected.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces corner-tree sums, a class of two-parameter iterated sums over image grids, and proposes a recursive dynamic program (Eq. (4)) to compute them. It defines the Fast Iterated Sums (FIS) layer, a differentiable tensor-to-tensor layer based on these sums, and evaluates it on CIFAR-10/100 image classification and MVTec AD texture anomaly detection. The central claims are that the corner-tree construction yields a substantially larger linear-time-computable subset of the two-parameter sums signature of [24] than previously known, that the algorithm runs in O(n T1 T2) time and space, and that replacing ResNet blocks with FIS blocks gives competitive accuracy with fewer parameters and multiply-adds.","tokens_in":19902,"tokens_out":8265,"duration_ms":78847,"significance":"If the complexity and expressiveness claims hold, this is a useful contribution: it connects permutation-pattern counting techniques to tensor feature extraction and provides a novel linear-cost layer with a clean mathematical interpretation. The empirical results, especially the CA-FIS ablation and the anomaly detection results, give initial evidence that the layer is more than a theoretical curiosity. The paper ships code and the recursive formula is machine-checkable, which is a strength. However, the significance is tempered by the lack of a formal complexity proof in the text, unquantified expressiveness claims, the absence of uncertainty estimates for the headline experimental numbers, and the omission of key hyperparameter values.","major_comments":[{"comment":"The complexity claim O(n T1 T2) is asserted without a cost model for the cumsum operation. Eq. (5) defines cumsum as a sum over a quadrant, and a naive per-pixel evaluation of this sum would cost O(T1 T2) per pixel, i.e., O(T1^2 T2^2) per edge. The text does not state that each directional cumsum is computed by a constant number of prefix/infix scans over the grid, nor does it provide pseudocode to substantiate the bound. Since the experiments use linear/NE trees of depth proportional to n (Section 5.1), the recursive computation along a chain performs one full-grid CTPS per level; this is still O(n T1 T2) only if each level's cumsum is linear in the grid size. Please provide a formal proof or annotated pseudocode with an explicit cost model.","section":"Section 3.2, Eqs. (4)-(5)"},{"comment":"The paper claims that a 'substantially larger subset' of the two-parameter sums signature is computable in linear time, but it never quantifies the size of this subset relative to the linear-time subset of [24] or to the full signature. The practical success of the FIS layer is therefore supported only by the specific random-tree configurations used in the experiments; no evidence is given that the chosen corner trees are representative or expressive enough for general image features. This is not a criticism of the algorithm's correctness, but it is a load-bearing assumption for the claim that the FIS layer is a generally useful primitive.","section":"Section 1 and Section 5.1"},{"comment":"The headline claim in the abstract that a smaller network with FIS blocks achieves 'similar accuracy (with a difference of only 0.1%)' rests on a single comparison: ResNet44 Downsample (94.47%) versus ResNet56 Base (94.37%) in Table 1. Other configurations show larger gaps (e.g., ResNet32 L23 is 2.90% below base), and Table 1 reports a single run per architecture with no standard deviations or seeds. Table 5 similarly reports single AUROC values per category. Given that Table 3 shows run-to-run variation of up to 0.85% standard deviation in a related setting, the 0.1% difference is within plausible training noise and should not be presented without repeated-seed results.","section":"Abstract and Tables 1, 3, 5"},{"comment":"The hyperparameters of the FIS layer, most importantly the number of corner trees N_T and the number of nodes per tree, are never reported for the experiments in Tables 1-6. Section 5.1 lists these as hyperparameters, but Section 6.1.3 only states that the max-plus semiring with random tree structure was adopted, and the appendix tables cover semiring, tree type, top-n threshold, latent dimension, and backbone, but not N_T or node counts. The code is a substitute, but the paper should state the values used so that the results are reproducible from the text alone.","section":"Section 5.1, Section 6.1.3, Appendix A"}],"minor_comments":[{"comment":"The contribution bullet claims the algorithm 'yields the first practical method for computing non-diagonal terms of the integrals-signature,' but Section 3 only gives a single example (the second-derivative approximation in Example 2) and does not explain how arbitrary non-diagonal terms are obtained; either expand this argument or soften the claim.","section":"Section 3, contribution bullet"},{"comment":"The caption states that the PatchCore comparison uses the model 'with the best average AUROC' chosen from [51], while FIS-AE is reported with a single default configuration; this asymmetry should be stated in the main text so that the comparison is not read as a like-for-like best-versus-default evaluation.","section":"Table 5 caption"},{"comment":"There is a typo in 'ImgaNet-pretrained ResNet' (should be 'ImageNet'); similar typos include 'conestellations' in Example 2, 'exaple' in the caption of Figure 10, and 'Secation' in Section 6.2.6.","section":"Section 6.2.2"},{"comment":"The generalization to order-p tensors is described as 'analogously' linear-time without details; if this is to remain a stated contribution, a brief explanation of how the directional scans generalize to p dimensions would be helpful.","section":"Section 4"}],"recommendation":"major_revision","confidential_remarks":"The mathematical core of the paper is likely correct, and the corner-tree algorithm is a genuine contribution. The main risks are the unproven complexity claim in the text and the overstatement of the empirical results, both of which are fixable. The expressiveness of the corner-tree subset is the deeper scientific question; I would ask the authors to compare with the prior linear-time subset of [24] or at least discuss the representational coverage. The missing hyperparameter values and lack of repeated-seed experiments should also be addressed before the paper can be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Core idea is new and worth engaging: they bring corner trees from permutation pattern counting to two-parameter iterated sums, give a recursive computation that looks correct, and package it as a differentiable layer. If the linear-time claim holds, it's a genuinely useful building block and the state-space-model connection is a nice bonus. The code is public, and the ablation on random tree structure is a point in their favor.\n\nThe soft spots are real but mostly addressable. The biggest one: the O(n T1 T2) complexity is asserted, not derived. The recursion in Eq. (4) nests cumulative sums whose cost per level is never analyzed. Pointing to an annotated implementation is not a proof. The claimed bound may well be true, but a referee cannot verify it from the text; this needs a short argument or pseudocode that counts grid scans. Second, the paper claims the computable subset is 'substantially larger' but never quantifies coverage or expressiveness, and the experiments use small random trees. That leaves the practical reach of the layer open. Third, the empirical reporting is too thin: the headline 0.1% accuracy match is one configuration with no error bars, and the anomaly detection table shows FIS-AE below PatchCore on most categories. The 'first practical method for non-diagonal id-signature terms' is asserted, not demonstrated.\n\nNone of this kills the paper. The circularity burden is low: the formalism is defined independently of the experiments, and the semiring/tree choices are normal model selection. The math in the core recursion is sound as far as it goes. I'd send this to a serious referee, with the explicit request that the complexity proof be made verifiable and the empirical claims brought in line with what is actually shown. Who should read it: people working on signature methods, SSMs, or cheap image feature extractors. Cite it if you build on the algorithm you find in the linked code; I'd hold off citing the empirical comparisons.","headline":"A genuinely new linear-time building block for iterated-sum features, with an unproven complexity claim and empirical results that need more rigor.","tokens_in":20462,"tokens_out":2144,"would_cite":true,"duration_ms":22097,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05A05","68Q25","68T07"],"pacs":[],"model":"deepseek-v4-flash","headline":"Corner trees make a large class of image iterated sums computable in linear time.","keywords":["iterated sums","two-parameter sums signature","corner trees","state-space models","image classification","anomaly detection","linear-time layer","tensor-to-tensor"],"falsifier":"Run the FIS layer on tensors of growing size and check that runtime stays proportional to $T_1T_2$: a ratio that grows with input size would falsify the linear-time claim. To test expressiveness, compare FIS features with the full two-parameter sums signature on small images; if the full signature separates image pairs that every random few-node corner tree fails to separate, the subset is too narrow.","tokens_in":19321,"feed_emoji":"🌳","tokens_out":6759,"duration_ms":62774,"temperature":0.7,"pith_summary":"Images are two-parameter data, and iterated-sum features that are cheap for sequences become expensive for images. This paper claims that a large class of such two-parameter sums—a subset of the two-parameter sums signature—can actually be computed in linear time and space by reinterpreting each sum as an occurrence count of a \"corner tree.\" The authors package that algorithm as the Fast Iterated Sums (FIS) layer, a tensor-to-tensor layer usable in image networks. If correct, the FIS layer gives a subquadratic building block whose expressiveness comes from the same mathematical object that characterizes image data up to natural equivalence; in experiments, replacing ResNet blocks with FIS matches a larger ResNet's accuracy while cutting parameters and multiply-adds. That matters because it offers a linear-cost alternative to quadratic attention for high-dimensional image and video tensors.","feed_headline":"Corner-tree image features match a bigger ResNet, 20% cheaper","feed_subtitle":"A new FIS layer computes two-parameter sums in linear time and nearly matches ResNet56 on CIFAR-10.","key_machinery":"Corner trees, adapted from permutation-pattern counting, are the governing object: a rooted tree whose edges carry labels from the eight cardinal directions $\\{N, NE, E, SE, S, SW, W, NW\\}$, each interpreted as a two-point predicate (e.g., $NE(r,s)$ means $s$ is northeast of $r$). The corner tree sum over all assignments of vertices to pixel positions satisfying every edge predicate is re-expressed through the corner-tree pre-sum recurrence, which computes, at each pixel, the node function times the cumulative sums over each child's subtree along the relevant direction. Because cumulative sums along rows and columns make each level cost $O(T_1T_2)$, the whole tree costs $O(nT_1T_2)$; the same recurrence works over any commutative semiring, and the max-plus version is what the experiments use.","core_discovery":"The paper's central claim is that a significant subset of the two-parameter sums signature of [24] can be computed in linear time and space using corner trees. A corner tree sum assigns each vertex a learned function of the pixel value and each edge one of eight cardinal-direction predicates; the sum over all point configurations consistent with the tree is shown by Theorem 5 to equal the sum over all points of a recursively defined pre-sum built from cumulative sums. That recursion is the algorithm, and it runs in $O(n T_1 T_2)$ time and space for a tree with $n$ vertices and an order-two tensor of size $T_1 \\times T_2$, with the same pattern extending to order-$p$ tensors. Packaged as the FIS layer using random trees and the max-plus semiring, it replaces convolutional blocks in a ResNet: one configuration reaches 94.47% top-1 accuracy on CIFAR-10, matching ResNet56's 94.37% with about 20% fewer parameters and 23% fewer multiply-adds, and an FIS encoder in an autoencoder scores an average AUROC of 97.3% on the MVTec texture set.","pith_inferences":["The paper leaves the coverage of the corner-tree subset unquantified; a natural follow-up is to measure, on small images, how much of the full sums signature's separating power is retained by random few-node trees, and whether larger or learned trees narrow the gap.","Viewed as a higher-order generalization of state-space models, the FIS block suggests a family of image architectures where long-range pixel interactions are accumulated by directional cumulative sums; combining such blocks with a selection mechanism, as in sequential state-space models, is a testable extension the paper does not explore.","The same corner-tree recurrence could in principle be run backward to provide per-pixel attribution or saliency maps, since each vertex's contribution to the final sum is already a tensor at the layer's native resolution."],"forward_implications":["A strictly larger subset of the two-parameter sums signature is computable in linear time and space than was previously known, removing the polynomial bottleneck on those terms.","The FIS layer can serve as a drop-in replacement for convolutional or attention-like blocks: on CIFAR-10 the ResNet44-downsample configuration reaches 94.47% accuracy versus 94.37% for ResNet56, with about 20% fewer parameters and 23% fewer multiply-adds.","After discretization, the same algorithm gives the first practical route to non-diagonal terms of the id-signature of images, making more of that signature accessible for applications.","Because the method generalizes to order-$p$ tensors, video and multimodal tensors inherit the same linear-cost feature computation.","An autoencoder whose encoder is made of FIS layers reaches an average image-level AUROC of 97.3% on the MVTec AD texture categories, 1.2 points above the same autoencoder with a convolutional encoder."],"supporting_citations":[{"why":"Introduces the two-parameter sums signature whose subset is the object the algorithm computes.","marker":"[24]"},{"why":"Supplies the corner-tree idea and the linear-time permutation-pattern counting technique the algorithm adapts.","marker":"[34]"},{"why":"Introduces the image (id-)signature whose non-diagonal terms become computable after discretization.","marker":"[25]"},{"why":"Presents a related id-signature formalism that the paper links to for the non-diagonal terms.","marker":"[27]"},{"why":"Provides the ResNet architecture and training setup used as the classification baseline.","marker":"[46]"},{"why":"Provides the MVTec AD texture dataset and its normal/anomaly splits used in anomaly detection.","marker":"[35]"},{"why":"Is the comparison baseline and supplies the PatchCore feature-extraction and anomaly-scoring conventions the FIS-AE follows.","marker":"[51]"},{"why":"Is the inverse-transform autoencoder baseline and the reconstruction-error anomaly detection framework the FIS-AE adapts.","marker":"[54]"}],"fun_headline_variants":["FIS layer matches ResNet accuracy, 20% fewer params","Linear-time tensor layer rivals ResNet on CIFAR-10","Corner-tree sums: linear-time image features that beat ResNet size","Fast iterated sums: cheaper image features without accuracy loss","Tensor layer cuts ResNet cost 20% while holding accuracy"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The FIS layer's practical value rests on the unproven premise that the subset of the two-parameter sums signature computable by a few random corner trees is large and expressive enough to capture the pixel relationships that image tasks need.","fun_headline_variants_meta":{"raw":{"variants":["FIS layer matches ResNet accuracy, 20% fewer params","Linear-time tensor layer rivals ResNet on CIFAR-10","Corner-tree sums: linear-time image features that beat ResNet size","Fast iterated sums: cheaper image features without accuracy loss","Tensor layer cuts ResNet cost 20% while holding accuracy"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00026,"raw_usage":{"total_tokens":1658,"prompt_tokens":1083,"completion_tokens":575,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":699,"completion_tokens_details":{"reasoning_tokens":486}},"tokens_in":699,"tokens_out":575,"duration_ms":5411,"temperature":1.0,"reasoning_tokens":486,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T06:02:11.973640+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the FIS layer on tensors of growing size and check that runtime stays proportional to $T_1T_2$: a ratio that grows with input size would falsify the linear-time claim. To test expressiveness, compare FIS features with the full two-parameter sums signature on small images; if the full signature separates image pairs that every random few-node corner tree fails to separate, the subset is too narrow.","supporting_citations":[{"cited_title":"Two-parameter sums signatures and corresponding quasisymmetric functions","cited_arxiv_id":"2210.14247","evidence_quote":"Introduces the two-parameter sums signature whose subset is the object the algorithm computes."},{"cited_title":"Counting small permutation patterns","cited_arxiv_id":null,"evidence_quote":"Supplies the corner-tree idea and the linear-time permutation-pattern counting technique the algorithm adapts."},{"cited_title":"Harang, and Samy Tindel","cited_arxiv_id":null,"evidence_quote":"Introduces the image (id-)signature whose non-diagonal terms become computable after discretization."},{"cited_title":"A topological approach to mapping space signatures","cited_arxiv_id":null,"evidence_quote":"Presents a related id-signature formalism that the paper links to for the non-diagonal terms."},{"cited_title":"Image classification codebase","cited_arxiv_id":null,"evidence_quote":"Provides the ResNet architecture and training setup used as the classification baseline."},{"cited_title":"Mvtec ad–a comprehensive real-world dataset for unsupervised anomaly detection","cited_arxiv_id":null,"evidence_quote":"Provides the MVTec AD texture dataset and its normal/anomaly splits used in anomaly detection."},{"cited_title":"Towards total recall in industrial anomaly detection","cited_arxiv_id":null,"evidence_quote":"Is the comparison baseline and supplies the PatchCore feature-extraction and anomaly-scoring conventions the FIS-AE follows."},{"cited_title":"Attribute Restoration Framework for Anomaly Detection","cited_arxiv_id":"1911.10676","evidence_quote":"Is the inverse-transform autoencoder baseline and the reconstruction-error anomaly detection framework the FIS-AE adapts."}],"review_version":1}