{"id":"a70bb7d3-341a-4914-8603-b5d00e2b6553","arxiv_id":"2412.08579","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A single signature coefficient at any depth can be recovered as a linear combination of signature kernel evaluations, each a Goursat PDE solution, with parallel time O(L).","lead":"This paper introduces a way to compute a single high-level signature coefficient of a path using signature kernels rather than direct iterated integration. The method trades exponential serial work for heavy parallelism, with a claimed O(L) parallel time that grows independently of the coefficient depth.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The algorithm's O(L) guarantee depends on the unproved applicability of [38, Thm 3.5] to the modified scheme (4.3) for the axis-path PDE; if the scheme does not converge at O(2^{-gamma1-gamma2}) for this piecewise-constant coefficient, the recovered coefficient carries uncontrolled error.","rationale":"I read the paper in good faith. The central construction—differentiating a signature kernel with respect to component scalings, selecting anagram classes, and using a Vandermonde filter to suppress higher levels—is mathematically coherent: Lemma A.1 correctly identifies the surviving permutations, and the Vandermonde solve (2.8)/(2.5) gives the stated cancellation for levels n+1 through n+M. The |J|! versus 1/|J|! typo and the 'linear' wording are harmless in context. The genuinely load-bearing step is the numerical evaluation of the kernels in Theorem 3.2. The paper's Theorem 4.1 simply cites [38, Theorem 3.5] without showing that the modified stencil and the discontinuous coefficient satisfy its hypotheses, and the stated scheme omits the beta_i lambda_j scaling. This matches the reader's weakest_assumption, so I agree. The proposed experiment would settle whether the scheme converges at the advertised rate and whether the scaling is implemented correctly. If those checks pass, the verdict would not need to change; as it stands, CONDITIONAL remains appropriate.","tokens_in":22801,"tokens_out":23468,"duration_ms":251748,"concrete_test":"Take x(t) = a t on [0,1] and z the axis path; the axis-path kernel k_{x, beta lambda circle z} has a closed form via tensor exponentials of increments. Implement (4.3) with the scaling factor beta_i lambda_j explicitly included in the coefficient, and compare against the closed form for n = 2 and n = 4, all lambda in {-1,0,1}^n, beta in (0,1], over gamma1, gamma2 = 0..5. Verify the sup error decays like O(2^{-gamma1-gamma2}). Then, without the scaling factor in (4.3), run the full recovery on random piecewise-linear x (L = 100, n = 3..6, M = 1) and compare S(x)_I to the exact value from Chen's relation; if the result deviates by more than the predicted tolerance, the scaling omission is real.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 3.2 is a statement about exact signature kernels; the practical claim that each term k_{x_I, beta_i lambda circle z} can be evaluated in O(L) parallel time requires the finite-difference scheme (4.3). The paper states Theorem 4.1 as a citation of [38, Theorem 3.5], but gives no proof that the cited convergence bound applies to this stencil, nor to the axis-path PDE (4.2) whose coefficient dot(x)^{(m)}_t is piecewise constant and jumps at the n nodes of z. Moreover, (4.3) as written contains no factor of beta_i lambda_j in Delta_j x, while the kernel in Theorem 3.2 is evaluated at the scaled path lambda circle z; if the implementation follows the literal scheme, it solves a different PDE. If either issue materializes, the recovered signature coefficient inherits an uncontrolled numerical error and the claimed O(L) parallel complexity has no numerical basis. The algebraic construction of Theorem 3.2 itself appears sound; the vulnerability is at the PDE-solving step.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a method for recovering a single signature coefficient S(x)_I at arbitrary depth n without computing the full truncated signature. The construction is algebraic: a filter in the span of signatures is built by combining finite-difference approximations to mixed derivatives with respect to component-wise path scalings, and the inner product of the signature with this filter is evaluated as a linear combination of signature kernels. The kernels are computed by solving a Goursat PDE, and the paper claims a serial complexity of O(L n 2^n) and a parallel complexity of O(L). The main theoretical result is Theorem 3.2, which states that a Vandermonde-weighted finite-difference combination of kernels with an axis path converges to S(x)_I as the scaling depth M tends to infinity. The paper also includes error bounds, experiments on random paths, and an application to sparse N-step Euler schemes for CDEs.","tokens_in":22972,"tokens_out":32055,"duration_ms":340930,"significance":"The algebraic construction is elegant and appears correct: the anagram-class and order-isolation propositions are checkable, Theorem 3.2 is plausible and well-supported by the appendices, and the explicit factorial-decay error bound in Proposition 2.8 is a useful falsifiable prediction that the experiments reproduce. If the numerical PDE step is justified, this would be a novel complexity improvement for computing deep isolated signature coefficients, and the paper provides public code. The main weakness is also load-bearing: the displayed numerical scheme (4.3) is not proved to converge, the cited convergence theorem is not shown to apply to this specific stencil, and the scheme as written omits the β_iλ scaling required by Theorem 3.2. The practical claims, including the O(L) parallel complexity, are therefore conditional on a numerical step that the manuscript does not yet adequately justify.","major_comments":[{"comment":"The convergence of the numerical scheme is load-bearing but not established. The text says that the scheme (4.3) is proposed 'taking inspiration from [13,38,40]' and then labels Theorem 4.1 as [38, Theorem 3.5]. Since (4.3) is not shown to be the scheme of [38], the cited convergence theorem does not automatically apply, and no proof is given for the modified stencil or for the special piecewise-constant coefficient in (4.2). More seriously, (4.3) contains no factor of β_iλ_j, whereas Theorem 3.2 requires kernels of the form k_{x_I, β_i λ⊙z}; as written, the scheme solves the PDE for the unscaled axis path z. Please either prove convergence for (4.3), or use exactly the scheme from [38] whose convergence is proved, and specify explicitly how β_iλ enters each kernel evaluation. This is necessary to support the claimed O(L) parallel complexity.","section":"Section 4, Eq. (4.3) and Theorem 4.1"},{"comment":"The parameterization of the axis path z is inconsistent. The definition z_t = (e_1 ∗ ⋯ ∗ e_n)_t for t ∈ [0,1], where each (e_i)_t is the linear path from 0 to e_i, is not a path on [0,1] under the standard concatenation convention; the PDE is then stated with s ∈ [m/d, (m+1)/d] and 'node at i/d', while the grid P_{γ1,γ2} uses j up to 2^{γ2} n. Depending on the intended convention, the segment speed n appears in the PDE coefficient, and the claimed scheme (4.3) may not correspond to the same path as Theorem 3.2. Please fix the definition of z, the interval for s, and the grid so that (4.2)–(4.3) describe the same path used in the algebraic results.","section":"Section 4, Eq. (4.2) and definition of z"},{"comment":"The exactness condition on D^{(n)}_λ is misstated. For the forward and central mixed differences used in the paper, the relevant property is exactness on the monomial λ_1⋯λ_n, together with the annihilation of monomials with repeated or missing variables, at the level-n contribution. The statement that D^{(n)}_λ is 'exact on linear functions of λ_1,...,λ_n' is not the needed condition, and a difference operator exact only on affine functions would not satisfy equation (2.6). Proposition 2.4 currently says the result follows immediately, but the verification that D^{(n)}_λ((λ_1+⋯+λ_n)^n) = n! is a nontrivial combinatorial fact. Please correct the definition and include this verification.","section":"Section 2, Notation 2.3 and Proposition 2.4"}],"minor_comments":[{"comment":"For the linear path y_t = te, the signature coefficient is S(y)_J = 1/|J|!, not |J|!; the sentence claiming that 'S(y)_J = |J|!' extracts the anagram class weighted by n! is incorrect as written. The displayed component-wise limit in (3.1) also appears to describe the filter based on z rather than S(β_iλ⊙x_I), whose limit would carry the coefficients S(x_I)_J.","section":"Section 3, paragraph before Proposition 3.1"},{"comment":"The proof of Proposition 3.1 cites Proposition 2.6, but the argument is that of Proposition 2.1; please correct the cross-reference.","section":"Section 3, proof of Proposition 3.1"},{"comment":"If Theorem 4.1 is intended as a verbatim citation of [38, Theorem 3.5], the paper should state explicitly that (4.3) is the scheme from [38]; otherwise the label 'Theorem 4.1 ([38, Theorem 3.5])' is misleading.","section":"Section 4, Theorem 4.1"},{"comment":"The inclusion K_J ⊂ K_I is asserted without specifying the identification of grid points, time intervals, and the extension of the central-difference nodes; a short explicit mapping would make the batch-retrieval claim easier to verify.","section":"Section 4.1"},{"comment":"There are several small typos and notational inconsistencies: 'singular coefficient' in the abstract should be 'single coefficient'; the title line contains spacing artefacts; and in (4.2), 't = i/d' should be a statement about s, with the convention for the segment length made consistent.","section":"Throughout"},{"comment":"In the condition (2.9) and the uniform-choice calculation, the paper should specify the constant C that makes the displayed O(M^{n+1}2^M) bound compatible with (2.9); the current text leaves the choice implicit.","section":"Section 2, Proposition 2.6 and Example 2.7"}],"recommendation":"major_revision","confidential_remarks":"To the editor: the algebraic core of the paper appears sound and the topic is well suited to a numerical analysis journal. The main risk is the numerical PDE step: the displayed scheme does not include the β_iλ scaling required by Theorem 3.2, and the convergence theorem is cited rather than proved for the modified stencil. These are fixable in revision, which is why I recommend major revision rather than rejection. I would also ask the editor to verify, possibly through the public code, whether the implementation actually uses the scaling factor; if it does, the paper should say so explicitly, and if it does not, the experiments need to be rerun with the corrected scheme."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline: this is a genuinely new algorithm for pulling out individual signature coefficients at arbitrary depth using signature kernel filters, and the main algebraic construction is sound. I'd send it to review, but the numerical PDE section needs work before I'd trust the O(L) complexity claim.\n\nWhat's new: the combination of scaling derivatives, Vandermonde zeroing of intermediate levels, and an axis path whose signature is a delta at a single permutation. That's a clever filter. Theorem 3.2 and Proposition 2.6 are proven in the appendices and the derivations check out modulo a few typos. The batch retrieval observation (Section 4.1) is a nice bonus.\n\nThe soft spots are concentrated in the numerics. The scheme (4.3) is introduced as \"inspired by\" earlier work and Theorem 4.1 simply cites [38, Thm 3.5] for convergence. That is not enough: the stencil is modified, and the coefficient in the axis-path PDE (4.2) is piecewise constant with jumps. The reader is left to guess whether the O(2^{-gamma1-gamma2}) bound still holds. There's also a suspicious scaling in the definition of Delta_j x_t (the denominator 2^{gamma2} looks like a mixing of t and s steps), and the scheme as written does not show the beta_i lambda_j factors needed for Theorem 3.2. These are fixable, but they are more than cosmetic.\n\nThere are also a couple of internal inconsistencies worth fixing: S(y)_J is written as |J|! where it should be 1/|J|! (Section 3 and the intro), and Notation 2.3 says exact on \"linear functions\" when the finite differences are exact on multilinear monomials. Minor, but they'll confuse readers.\n\nOne more thing: the runtime comparison in Figure 3 pits serial Chen against parallel kernels. That's not apples-to-apples, since Chen's relation can also be parallelized (O(Ln) vs O(L)). The claimed \"factor of n\" is still real in the parallel setting, but the figure overstates it.\n\nAll in all, the contribution is real and the math is mostly there. The numerical analysis gap is the main thing holding it back. With a proper convergence proof (or a more careful statement of which scheme actually inherits the bound), it would be a solid paper for the signature methods community. I'd bring it to a reading group, and I'd cite it once the numerics are cleaned up.\n\nRecommendation: send to peer review. It deserves a serious referee, but expect heavy revisions on Section 4.","headline":"Genuinely new algebraic filter for sparse signature coefficients; the numerics section needs a real convergence proof before the complexity claim is solid.","tokens_in":23556,"tokens_out":10034,"would_cite":true,"duration_ms":97403,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60L10","65Y05"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that any single signature coefficient of a path at any depth can be recovered from $O(2^n)$ signature kernel evaluations, each reducible to an $O(L)$ parallel Goursat PDE solve, bypassing the exponential cost of…","keywords":["path signatures","signature kernels","sparse coefficient recovery","iterated integrals","Goursat PDE","Vandermonde systems","GPU parallel computation","sequential data"],"falsifier":"Fix a piecewise-linear path $x$ and a multi-index $I$, compute the reference value $S(x)_I$ by direct iterated integration or a high-truncation Chen computation, and compare it with the kernel-filter recovery at increasing dyadic orders $\\gamma_1 = \\gamma_2$ of scheme (4.3). The paper's claim predicts the difference decays like $O(2^{-\\gamma})$ and approaches zero; a plateau, or a limit different from $S(x)_I$, would show that the numerical premise of Theorem 4.1 does not hold for the axis-path case.","tokens_in":22515,"feed_emoji":"⚡","tokens_out":13127,"duration_ms":122318,"temperature":0.7,"pith_summary":"The paper proposes a way to compute one iterated integral, one signature coefficient, of a path without computing the whole truncated signature. The idea is to build a filter in signature space whose inner product with a path's signature is exactly the desired coefficient, and then to express that inner product as a linear combination of signature kernels. Because each signature kernel solves a Goursat PDE, every kernel evaluation can be done in parallel in $O(L)$ time, so the depth of the coefficient stops being a bottleneck: the full recovery runs in $O(L)$ parallel time at the price of $O(2^n)$ kernel evaluations. This matters because signature coefficients are the feature basis for many machine-learning methods on sequential data, and existing dense or single-coefficient algorithms scale polynomially with depth.","feed_headline":"Deep signature coefficients from O(2^n) kernel solves","feed_subtitle":"A kernel filter pulls any iterated integral from a path in parallel time that no longer grows with depth.","key_machinery":"The load-bearing object is a filter in signature space, $F = \\sum_{i=0}^M \\alpha_i D^{(n)}_{\\lambda} S(\\beta_i \\lambda \\odot z)\\big|_{\\lambda=0}$, paired with the identity that $\\langle S(x_I), S(y) \\rangle$ is the signature kernel $k_{x_I, y}$. The axis path $z = (e_1 * e_2 * \\cdots * e_n)_t$ has signature $S(z)_J = 1$ when $J = (1, \\ldots, n)$ and $0$ for the other permutations of $(1, \\ldots, n)$, so it isolates a single ordering of the letters; the derivative $D^{(n)}_{\\lambda}$ removes every multi-index whose letters are not a permutation of $I$. A generalized Vandermonde system $B_{n,M} \\alpha = e_1$ selects the $\\alpha_i, \\beta_i$ so that the combined filter keeps level $n$ intact and annihilates levels $n+1$ through $n+M$, while the factorial decay of signature levels bounds the remaining tail. The whole construction is efficient because the signature kernel solves a Goursat PDE, for which the paper adapts the parallel finite-difference scheme (4.3).","core_discovery":"The central result is Theorem 3.2: for any $x \\in C^1([0,1], \\mathbb{R}^d)$ and multi-index $I$, there exist scalars $\\alpha_i(M)$ and $\\beta_i(M)$ such that the sum $\\sum_{i=0}^M \\alpha_i D^{(n)}_{\\lambda} k^{\\lambda-\\beta_i}_{x_I, z}\\big|_{\\lambda=0}$ converges to $S(x)_I$ as $M \\to \\infty$, where $z$ is the axis path $e_1 * e_2 * \\cdots * e_n$. The operator $D^{(n)}_{\\lambda}$ is a finite difference chosen to be exact on linear functions, and the Vandermonde choice of $\\alpha_i, \\beta_i$ zeros signature levels $n+1, \\ldots, n+M$, leaving only the factorial-decaying tail as error. The kernel $k$ solves the Goursat PDE $\\partial^2 k/\\partial t \\partial s = \\langle \\dot{x}_t, \\dot{y}_s \\rangle k$, and for the axis path the coefficient reduces to a single piecewise-constant channel of $x$, which is what makes the $O(L)$ parallel evaluation possible. The same filter construction generalizes to block sums of permuted coefficients (Theorem 3.4), and with truncated kernels the anagram-class recovery is exact (Proposition 2.4).","pith_inferences":["If the paper's recovery claim is right, the same filter idea could become a general sparse-signature query primitive: any coefficient or linear combination that one can encode as the support of an axis-like path could be recovered by the same kernel expansion, possibly by combining this method with signature-inversion techniques to build filters for arbitrary groups of coefficients.","Because the axis-path kernel PDE has a piecewise-constant coefficient on each subinterval, one could replace the finite-difference solver with an exact stepwise computation using the tensor-exponential form of the kernel on each cell, which would remove the discretization error that the paper currently inherits from the numerical scheme.","The paper fixes the finite-difference step size and uses small scaling depths ($M = 1$ or $2$) in experiments; the error bound in Proposition 2.8 suggests an adaptive strategy that chooses step size and $M$ per coefficient could reduce the number of kernel evaluations, especially for deep coefficients where factorial decay already suppresses the tail."],"forward_implications":["A single signature coefficient at depth $n$ can be computed in $O(L)$ parallel time (serial cost $O(L n 2^n)$), so on GPU hardware the depth of the needed feature no longer multiplies the runtime the way it does with Chen's relation.","Any evaluation of a sparse linear functional on the signature, such as a sparse regression model over path features, can be restricted to exactly the coefficients with nonzero weight and thereby skip the exponential dense tensor computation entirely.","When one coefficient is computed on the refined PDE grid, the stored grid contains the kernels for all its initial-segment sub-coefficients (and, with forward differences, all sub-coefficients), so whole families of related coefficients come out of the same computation at no extra kernel cost.","For sparse CDEs whose directional graph has maximum out-degree $\\Delta_+$, the $N$-step Euler scheme needs only $O(\\Delta_+^N)$ signature coefficients rather than $O(d^N)$, and for regular graphs the scheme sparsity approaches $m^{1-N}$, keeping high-order Euler schemes practical."],"supporting_citations":[{"why":"Supplies the Goursat PDE characterization of the signature kernel and the convergence theorem that the numerical scheme is said to inherit.","marker":"[38]"},{"why":"Provides the explicit inverse of the generalized Vandermonde matrix used to select the weights $\\alpha_i$ and scalings $\\beta_i$.","marker":"[1]"},{"why":"Gives the factorial-decay bound on signature levels used to control the residual error beyond level $n+M$.","marker":"[29]"},{"why":"Introduced the finite-difference stencil for the Goursat problem that scheme (4.3) adapts.","marker":"[13]"},{"why":"Cited as a further Goursat-solver reference behind the adapted numerical scheme.","marker":"[40]"},{"why":"Chen's relation, used to derive the axis-path signature that isolates a single ordered coefficient.","marker":"[8]"},{"why":"Establishes existence and uniqueness for the Goursat problem satisfied by the kernel.","marker":"[26]"}],"fun_headline_variants":["Kernel filters extract deep signature coefficients fast","Sparse coefficients from any depth via kernel sums","O(L) kernel method isolates iterated integrals","PDE-based kernels recover sparse signature terms"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole procedure inherits its accuracy from the way the kernel equation is solved numerically, and the paper assumes, without proof, that the existing error bound applies to the modified numerical scheme used for the axis-path case; if that assumption fails, the recovered coefficient carries an unknown error.","fun_headline_variants_meta":{"raw":{"variants":["Kernel filters extract deep signature coefficients fast","Sparse coefficients from any depth via kernel sums","O(L) kernel method isolates iterated integrals","PDE-based kernels recover sparse signature terms"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00031,"raw_usage":{"total_tokens":1813,"prompt_tokens":1037,"completion_tokens":776,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":653,"completion_tokens_details":{"reasoning_tokens":719}},"tokens_in":653,"tokens_out":776,"duration_ms":9191,"temperature":1.0,"reasoning_tokens":719,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T17:46:50.942804+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Fix a piecewise-linear path $x$ and a multi-index $I$, compute the reference value $S(x)_I$ by direct iterated integration or a high-truncation Chen computation, and compare it with the kernel-filter recovery at increasing dyadic orders $\\gamma_1 = \\gamma_2$ of scheme (4.3). The paper's claim predicts the difference decays like $O(2^{-\\gamma})$ and approaches zero; a plateau, or a limit different from $S(x)_I$, would show that the numerical premise of Theorem 4.1 does not hold for the axis-path case.","supporting_citations":[{"cited_title":"Salvi, T","cited_arxiv_id":null,"evidence_quote":"Supplies the Goursat PDE characterization of the signature kernel and the convergence theorem that the numerical scheme is said to inherit."},{"cited_title":"Arafat and M","cited_arxiv_id":null,"evidence_quote":"Provides the explicit inverse of the generalized Vandermonde matrix used to select the weights $\\alpha_i$ and scalings $\\beta_i$."},{"cited_title":"Lyons, Rough paths, signatures and the modelling of functions on streams , International Congress of Mathema- ticians, Seoul, (2014)","cited_arxiv_id":null,"evidence_quote":"Gives the factorial-decay bound on signature levels used to control the residual error beyond level $n+M$."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduced the finite-difference stencil for the Goursat problem that scheme (4.3) adapts."},{"cited_title":"W azwaz, On the numerical solution of the goursat problem , Applied mathematics and computation, 59 (1993), pp","cited_arxiv_id":null,"evidence_quote":"Cited as a further Goursat-solver reference behind the adapted numerical scheme."},{"cited_title":"Chen, Iterated integrals and exponential homomorphisms, Proceedings of the London Mathematical Society, 3 (1954), pp","cited_arxiv_id":null,"evidence_quote":"Chen's relation, used to derive the axis-path signature that isolates a single ordered coefficient."},{"cited_title":"Lees, The goursat problem, Journal of the Society for Industrial and Applied Mathematics, 8 (1960), pp","cited_arxiv_id":null,"evidence_quote":"Establishes existence and uniqueness for the Goursat problem satisfied by the kernel."}],"review_version":1}