{"id":"5a6429dc-9b30-4405-bfd5-24cd28676829","arxiv_id":"2501.07145","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"KSig implements GPU-accelerated signature kernel algorithms and adds a tensor-sketch based random feature method, RFSF-TS, with O(ML(Q log Q + Dd)) complexity.","lead":"KSig is a GPU-accelerated Python package for computing signature kernels on time series, with exact and randomized algorithms. It also introduces a tensor-sketch variant of random Fourier signature features that is faster than previous projection-based variants while giving comparable accuracy.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"RFSF-TS is probably unbiased, but its variance is unanalyzed and the new-method claims rest on a single seedless MAPE benchmark; this should be tested before the abstract's 'strong performance' claim is treated as established.","rationale":"The reader's weakest assumption identifies the RFSF-TS construction and the MAPE proxy as the fragile points. My independent re-derivation of Eq. (15) indicates that the strict unbiasedness worry is probably not the real defect: the tensor sketch is linear, and the count-sketch operators are independent of the RFF maps, so the composed estimator is unbiased for the truncated signature kernel. The genuinely load-bearing issue is therefore the absence of a variance analysis for the composed estimator and the thinness of the empirical support for the new algorithm: one synthetic MAPE comparison without error bars, no downstream validation for RFSF-TS, and no theoretical bound connecting count-sketch variance to signature-feature norms. These gaps do not invalidate the package: the dual algorithms are standard, the code is public, the complexity tables are plausible, and the empirical curves show the expected qualitative behavior. But they do mean the new-method claim in the abstract is not yet fully established. Since the reader already assigned CONDITIONAL, my stress-test does not move the verdict; it sharpens the condition by moving the emphasis from unbiasedness to variance and evaluation reliability.","tokens_in":28021,"tokens_out":16353,"duration_ms":182572,"concrete_test":"Rerun the Section 4.2 MAPE experiment with 30 independent seeds (fresh RFF frequencies and tensor-sketch hash/sign functions) at M=5, N=20, L=100, D=Q=100, and also with N=100, and report median plus 10th-90th percentiles for RFSF-TS, RFSF-TRP, RFSF-DP-1D, and RFSF-DP. If the RFSF-TS percentile band overlaps RFSF-TRP or RFSF-DP-1D at fixed feature-map size, or if the 90th percentile exceeds twice the median at any tested F, then the 'strong performance' claim is not supported and the variance concern is confirmed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Unbiasedness in the strict sense is not the weak point: because the tensor sketch is linear in the tensor argument and the count-sketch hashes/signs are independent of the RFF draws, E[<PhiTS_m(x),PhiTS_m(y)> | RFF] = <Phi_m(x),Phi_m(y)> and the RFF expectation gives the exact level-m signature kernel. So Eq. (15) is a valid Monte Carlo construction, even though the paper omits the derivation. The load-bearing gap is variance and evaluation. The paper cites [22, Lem. 3] for a single count-sketch variance bound, but RFSF-TS is a sum over O(L^m) recursively sketched tensor terms, possibly with level-wise self-normalization (Section 6.3), and no bound is provided showing the variance stays controlled as L, M, or Q grow. Empirically, the abstract's 'strong performance compared to existing algorithms' rests on Fig. 3 alone: one synthetic Brownian-Motion MAPE experiment with M=5, N=20, L=100, no error bars, and no downstream task using RFSF-TS. If tensor-sketch variance is large for typical signature-feature norms, the scalability and downstream benefits claimed in Fig. 1 and Remark 1 would not transfer to real applications.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces KSig, a Scikit-Learn compatible Python package for GPU-accelerated computation of signature kernels on sequential data. It presents dual algorithms (the exact truncated signature kernel and the signature-PDE kernel) and primal low-rank feature algorithms (RFSF with diagonal projection, tensor random projection, and a newly proposed tensor-sketch variant, RFSF-TS). For each method the paper gives pseudocode-level recursion, complexity tables, code examples, and scalability experiments on an A100 GPU, including memory/runtime comparisons and MAPE accuracy against the exact truncated kernel. The central claims are that KSig enables Gram-matrix computation for sequences of length up to 10^5 via primal methods, that the new RFSF-TS achieves approximation quality comparable to or better than existing RFSF variants at lower memory cost, and that the package integrates cleanly with standard Scikit-Learn workflows.","tokens_in":28303,"tokens_out":5234,"duration_ms":49937,"significance":"If the claims hold, KSig would be a practically valuable open-source toolbox for kernel-based learning on time series, particularly because it provides GPU kernels, a dual/primal split, and a new tensor-sketch feature map that could reduce the memory footprint of random Fourier signature features. The paper's strengths are its clear code examples, plausible complexity tables, and a publicly available implementation. The exact dual algorithms are standard and well motivated. The main caveat is that the new RFSF-TS method, which is highlighted in the abstract as giving 'strong performance', is not supported by a variance analysis and is evaluated in only a single synthetic MAPE experiment without error bars or any downstream task. Thus the significance of the central new contribution is currently not fully established, although the package itself is likely to be useful to practitioners.","major_comments":[{"comment":"The paper introduces RFSF-TS as a new algorithm but does not prove or even state explicitly that the feature map in Eq. (15) provides an unbiased estimate of the truncated signature kernel. The text only says that the tensor sketch of a tensor product is again a count sketch and cites [22, Lem. 3] for the variance of a single count-sketch inner product. However, the RFSF-TS recursion aggregates O(L^m) recursively sketched tensor terms, and Section 6.3 describes an additional level-wise normalization step. The cited lemma does not cover this composed estimator. Since the abstract's 'strong performance' claim relies on the approximation quality of this new method, the paper should either provide a derivation of unbiasedness and a variance bound under the recursion, or clearly state that such a guarantee is not yet available and temper the corresponding claim.","section":"§3.5, Eq. (15)"},{"comment":"The MAPE experiments constitute the only quantitative evidence for the claim that RFSF-TS 'gives strong performance compared to existing algorithms'. Fig. 3 reports a single run on a synthetic Brownian motion dataset with M=5, N=20, L=100, and no error bars, confidence intervals, or multiple random seeds. Because RFF and tensor sketches are randomized, the differences between RFSF-TS and RFSF-TRP in Fig. 3 may be within noise. The paper should either report means and standard deviations over several independent repetitions, or provide a downstream learning task where RFSF-TS is compared with RFSF-TRP. The same lack of error bars applies to Figs. 4 and 5. Without this, the assertion in the abstract is not statistically substantiated.","section":"§4.2, Figs. 3–5"},{"comment":"The classification examples in the paper use RFSF-TRP (PenDigits, Section 3.6) and the exact dual kernel (FingerMovements, Section 2.4), but never use the new RFSF-TS method. Consequently, the paper does not demonstrate that RFSF-TS's approximation accuracy translates to useful downstream performance. Given that the abstract highlights RFSF-TS as a central contribution, the absence of any end-to-end evaluation of this method is a significant gap. I recommend either adding a classification or regression experiment that uses RFSF-TS, or revising the abstract and conclusion to present RFSF-TS as a promising but not yet fully validated variant.","section":"§3.6 and §4 (deployment experiments)"}],"minor_comments":[{"comment":"The double-difference operator in Eq. (1) contains a typo: 'k(x_i, y_{j-1}, x_i)' should be 'k(x_i, y_{j-1})'.","section":"§2.1, Eq. (1)"},{"comment":"The word 'untruecated' should be 'untruncated'.","section":"§2.3"},{"comment":"The variable name 'K_sig_pde' in the code differs from the earlier 'k_sig_pde' in the same snippet; please make the capitalization consistent.","section":"§2.4, code snippet"},{"comment":"The statement 'We leave it a straightforward exercise for the reader to check that this indeed provides an unbiased approximation' is not appropriate for a central property of the proposed methods; please state the unbiasedness result explicitly or provide a short derivation.","section":"§3.2"},{"comment":"The MAPE equation is referred to as 'eq. 4.2' but no equation number appears in the text; please number the equation or remove the reference.","section":"§4.2, MAPE formula"},{"comment":"The synthetic Brownian motion experiments do not report the bandwidth of the RBF/RFF kernel or the specific random seed(s). Please include these details to improve reproducibility.","section":"§4.2, experiments"},{"comment":"The text says 'RFSF-TS and RFSF-TRP offer lower MAPE for a given feature map size F', but at the smallest feature map sizes the RFSF-DP-1D curve appears competitive; please rephrase to avoid overstatement.","section":"§4.2, Fig. 3"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is heavily self-citing (refs [35] and [36] are by the same authors) and builds directly on the authors' own RFSF work. This is not circularity, but the novelty of RFSF-TS relative to [35] should be clearly delineated. The paper is a user's guide / software paper; it may be better suited for a software-focused venue (e.g., JMLR MLOSS) than a general stat.ML research venue unless the new method receives stronger theoretical or empirical validation. The referee report focuses on the lack of a variance analysis and on the thin empirical support for the new RFSF-TS, both of which are load-bearing for the abstract's 'strong performance' claim."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take on KSig. It's a user guide with one new algorithmic piece: RFSF-TS, a tensor-sketch variant of RFSF. The package itself is real: public code, GPU-accelerated via CuPy, sklearn-compatible, with dual and primal algorithms. For someone who wants to actually compute signature kernels, this is the most usable package I know. The complexity tables are careful and match the code, and the scalability experiments (Fig. 1/2) are informative: dual methods die at L~10^3, primal reach L~10^5. The paper credits prior work properly; self-citation here is about the authors' own RFSF papers, which is fair given they are building directly on it.\n\nThe soft spots are concentrated on the new method. Eq. (15) is a valid Monte Carlo construction—the stress-test note is right that unbiasedness follows from linearity of the tensor sketch and independence of the count-sketch hashes from the RFF draws, so the missing derivation is not fatal. But there is no variance analysis for the composed RFSF-TS estimator, and no bound showing the variance stays controlled as L, M, or Q grow. The empirical case for 'strong performance compared to existing algorithms' rests almost entirely on Fig. 3: a single Brownian-motion MAPE experiment with no error bars, no repeated seeds, and no downstream task using RFSF-TS. The PenDigits deployment example uses RFSF-TRP, not RFSF-TS. That is a real gap. If the tensor-sketch variance is high for typical signature-feature norms, the claimed scalability would not carry over to real applications.\n\nAlso note: the paper says 'strong performance' in the abstract, but the evidence is one figure. That's an overclaim relative to what is shown. The rest of the guide—dual algorithms, PDE kernel, RFF, diagonal projection, TRP—is exposition of known work, but it's well organized and the implementation details (memory-saving antidiagonals for KSigPDE, for example) are genuinely useful.\n\nVerdict: this deserves a serious referee. A software paper with this much public, runnable code is worth reviewing, and the RFSF-TS variant is worth testing properly. The referee should ask for variance analysis or at least a clear statement of the open problem, error bars/repeated seeds on the MAPE experiments, and at least one downstream task using RFSF-TS. If those are added, it becomes a clean accept. As is, it's a conditional accept—the package is a real contribution, the new method is plausible but under-validated.","headline":"KSig is a genuinely useful software paper with one new algorithmic variant; the package is solid, but RFSF-TS is under-validated and the 'strong performance' claim outruns the evidence.","tokens_in":28811,"tokens_out":2323,"would_cite":true,"duration_ms":22034,"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":"KSig pushes signature-kernel Gram matrices past 100,000 time steps","keywords":["signature kernel","random Fourier signature features","tensor sketch","GPU acceleration","Gram matrix","time series classification","kernel methods","random features"],"falsifier":"Measure the empirical variance of the RFSF-TS estimator against the exact truncated signature kernel for a fixed Brownian motion path while increasing truncation level $M$ and projection size $Q$; if the relative error grows much faster than $1/\\sqrt{Q}$ or the memory advantage over RFSF-TRP disappears at the claimed scales, the central scalability claim is false.","tokens_in":27831,"feed_emoji":"⚡","tokens_out":6905,"duration_ms":57765,"temperature":0.7,"pith_summary":"The paper introduces KSig, a GPU-accelerated Python package for computing signature kernels on sequential data, and argues that its combination of dual (kernel-trick) and primal (random-feature) algorithms lets kernel methods scale to time series that were previously out of reach. The central new item is RFSF-TS, a tensor-sketch variant of Random Fourier Signature Features that replaces expensive tensor products with FFT-based circular convolutions of count sketches. The paper reports that this feature map matches or beats the existing tensor-random-projection variant in accuracy at lower memory cost, with time complexity $O(ML(Dd+pQ\\log Q))$. If these claims hold, practitioners can compute Gram matrices for sequences of length $10^5$ or more with primal methods while exact dual methods remain usable at moderate lengths.","feed_headline":"KSig pushes signature-kernel Gram matrices past 100,000 time steps","feed_subtitle":"New tensor-sketch features cut memory while matching accuracy on long time series.","key_machinery":"The load-bearing object is the recursive signature feature map. The dual algorithms use the Chen-identity recursion that computes the truncated signature kernel level by level, while the primal algorithms replace the static kernel lift by random Fourier features. For RFSF-TS, the new machinery is the tensor sketch: a count-sketch-based map that sends a tensor product $x_1\\otimes\\cdots\\otimes x_m$ to the circular convolution of independent count sketches $\\mathrm{CS}_1(x_1)\\star\\cdots\\star\\mathrm{CS}_m(x_m)$, computed in $O(Q\\log Q)$ time via the FFT. The paper's recursion (15) applies this sketch at every level of the signature feature recurrence, which removes the need to form or store the tensor products.","core_discovery":"On its own terms, the paper's claim is that one unified package covers the practical range of signature-kernel computation. Exact truncated signature kernels and PDE-based untruncated kernels are implemented as dual algorithms that are quadratic in sequence length; Random Fourier Signature Features in four projection variants (DP, DP-1D, TRP, TS) form primal algorithms that are linear in sequence length. The new contribution, RFSF-TS, replaces each tensor product in the RFSF recursion with a circular convolution of independent count sketches evaluated by FFT, reducing the projection cost to $O(MLDd + MLpQ\\log Q)$ instead of the $O(MLD(d+pQ))$ of tensor random projections. Empirically, RFSF-TS and RFSF-TRP give the most accurate features for a given feature-map size, RFSF-TS uses less memory than RFSF-TRP, and diagonal-projection variants achieve the lowest absolute error when memory is the binding constraint. The experiments also show that projection size $Q$ matters more than static feature size $D$ for the two tensor methods.","pith_inferences":["Editorial inference: the tensor-sketch identity used here is not specific to signatures, so RFSF-TS-style sketches could be dropped into other tensorized random-feature approximations, such as polynomial-kernel feature maps, wherever memory is the bottleneck.","Editorial inference: the accuracy benchmark compares against the truncated signature kernel with $M=5$ and $D=Q$; a natural stress test is to measure whether RFSF-TS variance stays bounded as $M$ and $Q$ grow together on longer Brownian paths, since count-sketch variance is controlled by input norms.","Editorial inference: if the unbiasedness of the tensor-sketch recursion extends beyond stationary RBF kernels, the approach would transfer to non-stationary static kernels and to higher embedding orders $p>1$, where the paper's complexity analysis currently focuses on $p=1$."],"forward_implications":["Dual algorithms (the exact signature kernel and the PDE-based kernel) can process sequence lengths around $10^3$ on a 40 GB GPU, while primal algorithms reach $L\\ge 10^5$ under the same memory budget.","For a fixed feature-map size, RFSF-TS and RFSF-TRP give lower approximation error than the diagonal-projection variants, and RFSF-TS achieves this with a smaller memory footprint than RFSF-TRP.","Increasing projection size $Q$ reduces error for RFSF-TS and RFSF-TRP much more than increasing static feature size $D$, so $D$ should not be enlarged without a matching $Q$.","All four primal variants scale linearly in truncation level $M$, so higher-order signature information can be added without changing the asymptotic complexity.","The primal feature formulation lets downstream models such as linear SVM avoid the $N\\times N$ Gram matrix, reducing the dependence on the number of sequences from quadratic or cubic to linear in both time and memory."],"supporting_citations":[{"why":"introduces the signature kernel construction and the dynamic-programming recursion for the exact truncated signature kernel that KSig implements.","marker":"[14]"},{"why":"introduces Random Fourier Signature Features and the DP and TRP projection variants that the new tensor-sketch method extends.","marker":"[35]"},{"why":"introduces tensor sketches and the unbiasedness and variance guarantees used to justify replacing tensor products by FFT-based circular convolutions.","marker":"[22]"},{"why":"derives the PDE formulation of the untruncated signature kernel used as the second dual algorithm.","marker":"[27]"},{"why":"provides Random Fourier Features, the static feature map underlying all of the primal signature feature algorithms.","marker":"[23]"}],"fun_headline_variants":["Tensor sketches cut signature kernel memory and speed up GPU computing","KSig's new tensor-sketch algorithm scales signature kernels to 100k steps","GPU-accelerated KSig: tensor sketches slash memory for long time series","Signature kernel package KSig adds tensor sketches for faster, leaner scaling"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that composing independent count sketches through FFT circular convolutions inside the signature recursion preserves the unbiasedness and controlled variance of the RFSF estimator, so the accuracy seen on the benchmark carries over to real tasks.","fun_headline_variants_meta":{"raw":{"variants":["Tensor sketches cut signature kernel memory and speed up GPU computing","KSig's new tensor-sketch algorithm scales signature kernels to 100k steps","GPU-accelerated KSig: tensor sketches slash memory for long time series","Signature kernel package KSig adds tensor sketches for faster, leaner scaling"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000368,"raw_usage":{"total_tokens":1937,"prompt_tokens":871,"completion_tokens":1066,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":487,"completion_tokens_details":{"reasoning_tokens":987}},"tokens_in":487,"tokens_out":1066,"duration_ms":8828,"temperature":1.0,"reasoning_tokens":987,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T20:48:40.145524+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Measure the empirical variance of the RFSF-TS estimator against the exact truncated signature kernel for a fixed Brownian motion path while increasing truncation level $M$ and projection size $Q$; if the relative error grows much faster than $1/\\sqrt{Q}$ or the memory advantage over RFSF-TRP disappears at the claimed scales, the central scalability claim is false.","supporting_citations":[{"cited_title":"Kiraly and Harald Oberhauser","cited_arxiv_id":null,"evidence_quote":"introduces the signature kernel construction and the dynamic-programming recursion for the exact truncated signature kernel that KSig implements."},{"cited_title":"Random Fourier Signature Features","cited_arxiv_id":"2311.12214","evidence_quote":"introduces Random Fourier Signature Features and the DP and TRP projection variants that the new tensor-sketch method extends."},{"cited_title":"The Signature Kernel Is the Solution of a Goursat PDE","cited_arxiv_id":null,"evidence_quote":"derives the PDE formulation of the untruncated signature kernel used as the second dual algorithm."},{"cited_title":"Weighted sums of random kitchen sinks: Replacing minimization with randomization in learning","cited_arxiv_id":null,"evidence_quote":"provides Random Fourier Features, the static feature map underlying all of the primal signature feature algorithms."}],"review_version":1}