{"id":"7a502ad0-b13e-478e-aeda-e1219e33df8a","arxiv_id":"2512.14218","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.1,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"An exact algorithm recovers the linear map A from its third-order signature tensor G = A*C in expected O(d^4) time, replacing the Gröbner-basis method that previously solved this inverse problem.","lead":"The paper presents a new exact algorithm for recovering paths from their third-order signature tensors, running in expected O(d^4) elementary operations. The method replaces the existing Gröbner-basis approach with elementary Gauss transformations, making signature inversion practical at dimensions far beyond what previous exact methods could reach.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 4 as printed cannot execute its third upper transformation: the guard and denominator compare G_{d−2,d−1,d−1} with itself, so Q3 is never applied; Example 4.3's own computation needs Q3, so Algorithm 1 fails at s=d−2 on such inputs until this typo is fixed.","rationale":"The paper's central claim is an exact, efficient signature-inversion algorithm. The main algebraic line appears sound: the orbit reduction via upper/lower/diagonal Gauss transformations is constructive, Proposition 5.10 supplies a concrete upper transformation for generic points, and the generic-rank argument can be made rigorous because the relevant rank condition is an open condition and the consistency conditions are polynomial identities that vanish on a Zariski-open set. The randomized retry is informal but fillable; it is not the most dangerous issue. The most load-bearing concern is that the printed Algorithm 4 is genuinely broken: its third step is tautological and would divide by zero if reached, yet the paper's own example and Proposition 4.4 require that third step. Because Algorithm 1 calls up3 at s=d−2 for every d≥3, this is an executable failure in the algorithm as stated. This is a typographical/copyediting defect rather than a mathematical refutation—the correct formula is evident from Example 4.3 and Proposition 4.4—so it does not overturn the reader's CONDITIONAL verdict, but it confirms that the manuscript as printed is not reproducible and needs correction before acceptance. The reader already flagged the tautological condition in Algorithm 4 among the mechanical problems, but did not make it the weakest assumption; hence partial agreement.","tokens_in":15985,"tokens_out":33613,"duration_ms":258472,"concrete_test":"Implement Algorithm 4 exactly as printed and run it on the tensor G'' from Example 4.3 (equivalently, keep the tautological guard). The algorithm will skip Q3 and return Q2 Q1; applying the resulting transformation to G'' will not satisfy conditions (i)–(iv) of Theorem 3.2 for s=2, so Algorithm 1 cannot proceed to the next reduction. Then change the guard and denominator to G_{d−2,d−1,d−1} − G_{d−1,d−2,d−1}; with this correction, the algorithm applies the same Q3 as in Example 4.3 and the output satisfies Theorem 3.2. If the associated GitHub code already uses the corrected formula, this confirms the printed pseudocode is a typo; if it uses the printed formula, the code will fail on Example 4.3.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The printed Algorithm 4 (Section 4) contains a tautological condition and a zero denominator in its third step: 'if G_{d−2,d−1,d−1} ≠ G_{d−2,d−1,d−1} then Q3 ← I_d + (G_{d−1,d−2,d−2}−G_{d−2,d−1,d−2})/(G_{d−2,d−1,d−1}−G_{d−2,d−1,d−1}) E_{d−2,d−1}'. The guard is never true, and if it were, the denominator is 0. Proposition 4.4's proof and Example 4.3 both show that a third transformation Q3 is needed generically; in the example Q3 = I4 − (G''_{322}−G''_{232})/(G''_{233}−G''_{323}) E23 is applied after Q1,Q2. Since Algorithm 1 invokes up3(G) at s=d−2 for every d≥3, the algorithm as printed does not correctly handle inputs requiring this transformation. This is a concrete correctness bug in the central claim, not merely a formatting issue. The underlying mathematical construction is plausibly sound—the correct formula is obtained by replacing the second index in the denominator's first term with d−1—but as printed Theorem 1.1 is not executable. Related typos (Definition 5.6 index ranges, Theorem 3.2 proof case (2c)) should be checked in the same revision, but the Algorithm 4 bug is the one that directly makes Algorithm 1 fail.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents an algorithm for the exact recovery of an invertible matrix A from a third-order signature tensor G = A*C, where C is the fixed signature tensor of the axis path in dimension d. The method uses upper, lower, and diagonal Gauss transformations under the congruence action to bring G into the orbit of the core tensor C, then recovers A via the known trivial-stabilizer result. The main theorem (Theorem 1.1) claims that Algorithm 1 always returns A and runs in expected O(d^4) operations. The paper includes an OSCAR implementation, benchmarks against Gröbner-basis methods, and formal verification of several rational-function identities in low-dimensional cases.","tokens_in":16289,"tokens_out":5661,"duration_ms":44467,"significance":"If correct, this is a substantial contribution: it replaces the previous Gröbner-basis approach to third-order signature inversion with a polynomial-time expected algorithm in arbitrary dimension, and it comes with a reproducible implementation and machine-checked algebraic verifications. The core mathematical strategy — iterative reduction via generalized normal forms — is natural and, aside from the issues below, the proof structure is coherent. Credit is due for the explicit use of an independent uniqueness theorem (PSS19), the closed-form core tensor (AFS19), and for shipping code and timing comparisons. The main reservation is that the printed Algorithm 4 contains a concrete indexing error that makes the central algorithm fail on generic inputs as written, so the manuscript requires correction before the claims are executable.","major_comments":[{"comment":"The third upper transformation is not executable as printed. The guard 'if G_{d-2,d-1,d-1} ≠ G_{d-2,d-1,d-1}' is tautologically false, and the denominator in the same line is zero. Example 4.3 explicitly needs Q3, and Algorithm 1 invokes up3 at s=d-2 for every d≥3. The correct condition and denominator are G_{d-2,d-1,d-1} ≠ G_{d-1,d-2,d-1} and G_{d-2,d-1,d-1} - G_{d-1,d-2,d-1}, as used in the example's Q3. This is a load-bearing bug: as printed, Algorithm 1 does not terminate correctly on inputs requiring the third transformation. The mathematical construction appears sound, but the algorithm must be corrected.","section":"Section 4, Algorithm 4 (up3)"},{"comment":"The index ranges in Definition 5.6 are inconsistent with the claimed matrix size. The text says 'for 1≤a,b < s and 1< γ≤d−s−1', but M is a (d−s)^2 × (d−s) matrix and the accompanying Example 3.5 uses a,b running up to d−s. As written, M and B are undefined for most indices, so Algorithm 2 cannot be executed from this definition. The intended range is presumably 1≤a,b≤d−s and 1≤γ≤d−s, with the symmetry reduction explained in Remark 5.7. This needs correction in the revision.","section":"Definition 5.6"},{"comment":"The proof claims 'H_ijs = 0 with i>s≥j' for j=s, but in H∈(I_{s-1}⊕GL_{d-s+1})*C, the entry H_{i,s,s} is not generally zero (it can equal A_{i,s}(A_{s,s})^2). The desired vanishing J_{i,s,s}=0 follows from condition (ii) after applying the lower transformation: J_{i,s,s}=H_{i,s,s}-H_{s,i,s}=0. The written justification is therefore incorrect as stated, though the theorem is recoverable. The proof should be rewritten to avoid this false assertion.","section":"Theorem 3.2, proof case (2c)"}],"minor_comments":[{"comment":"The randomized retry step is not fully formalized. Over the reals, Okada's lemma gives measure-zero bad sets, but the algorithm is described over exact rational arithmetic, and the phrase 'random W' does not specify a distribution. A short remark on how randomness is implemented in exact arithmetic and why the success probability is 1 would remove ambiguity.","section":"Section 3, Algorithm 2 / Proposition 5.9"},{"comment":"The sentence 'This follows, for example, with the adjugate matrix of B and [Oka73, Lemma 1]' is very terse. Expanding this one or two lines would help the reader verify the generic solvability claim.","section":"Corollary 5.11"},{"comment":"The index conditions in part (i), 'i=j=k≤s or k≤min(s,i−1,j) or j≤min(s,i−1,k)', are hard to parse. A short explanation or a diagram indicating the corresponding tensor positions would improve readability.","section":"Theorem 2.3"},{"comment":"There is a typo: 'we provide all omitted proves' should read 'we provide all omitted proofs'. Also, the full-text title reads 'An Efficient Algorithm for Tensor Learning' while the arXiv title is 'An Efficient Algorithm for Path Recovery from Signature Tensors'; the consistency should be checked.","section":"Section 5, opening line"}],"recommendation":"major_revision","confidential_remarks":"The Algorithm 4 issue is clearly a fixable indexing typo rather than a fundamental flaw, but it is directly in the main algorithm and must be corrected before the theorem is substantiated. The manuscript would benefit from an editor's check of the final camera-ready version against the cited code repository, since the paper relies on OSCAR verifications and the printed formulas for correctness. The dependence on prior work (PSS19, AFS19) is appropriate and not a circularity concern."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the take: the paper's central idea is good and probably correct, but you cannot run Algorithm 4 as printed. The third transformation has a guard \"if G_{d−2,d−1,d−1} ≠ G_{d−2,d−1,d−1}\" and denominator \"G_{d−2,d−1,d−1}−G_{d−2,d−1,d−1}\", so Q3 is never applied and the denominator is zero. The paper's own Example 4.3 needs Q3 with denominator G''_{233}−G''_{323}, i.e., the second term should be G_{d−1,d−2,d−1}, not G_{d−2,d−1,d−1}. Because Algorithm 1 invokes up3 at s=d−2, this typo makes the central claim fail on the submitted example. That's a load-bearing bug, not a formatting issue.\n\nWhat's genuinely new: the reduction of third-order signature inversion to congruence normal forms via Gauss transformations, replacing Gröbner bases with an exact O(d^4) expected procedure. That is a real step over the previous baselines. The proof structure is credible: the main theorem follows from the stated propositions, and the OSCAR verification of the rational identities is real evidence for the low-dimensional cases. The author builds honestly on PSS19 and AFS19 for uniqueness and the core tensor; I don't see a circularity problem.\n\nThe soft spots beyond the typo: Definition 5.6's index ranges are inconsistent (it says \"1≤a,b<s\" for a (d−s)^2×(d−s) matrix) and need straightening. The randomized retry step is stated informally—\"in expectation\" is plausible, but the probability accounting isn't done. The proof of Theorem 3.2 has a couple of index slips in case (2c). None of these looks fatal to the underlying construction, but they add to the reproducibility burden.\n\nVerdict: this deserves a serious referee. The algorithm is a real contribution to rough-path signature inversion. I'd send it out with a request that the author fix the Algorithm 4 typo and the index ranges, and formalize the randomization. Once that is done, the result is likely solid. But as printed, I would not rely on Theorem 1.1, and I wouldn't cite it until the correction lands.","headline":"Genuine algorithmic advance for signature inversion, but the printed Algorithm 4 has a self-comparison typo that breaks the main algorithm on the paper's own example.","tokens_in":16833,"tokens_out":6218,"would_cite":false,"duration_ms":46578,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60L10","15A21","68W30","14Q15"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that every third-order signature tensor in the congruence orbit of the axis-path core tensor can be inverted exactly by a sequence of Gauss transformations, with expected O(d^4) arithmetic operations.","keywords":["path recovery","signature tensors","matrix-tensor congruence","Gauss transformations","linear systems","third-order signature","group orbits","computer algebra"],"falsifier":"Exhibit a tensor G = A*C for which the matrix M from Algorithm 2 becomes rank-deficient for every random coordinate change W, forcing the recursion to loop without terminating; or exhibit a non-identity A with A*C = C, contradicting the trivial-stabilizer theorem.","tokens_in":15787,"feed_emoji":"🧮","tokens_out":4591,"duration_ms":35568,"temperature":0.7,"pith_summary":"The paper claims that the inverse problem of rough path analysis — recovering a path from its third-order iterated-integrals signature — can be solved exactly and efficiently in any dimension d. Previous exact approaches modeled the signature as a system of d^3 polynomial equations in d^2 unknowns and solved it with Gröbner bases, which becomes impractical quickly. The new algorithm instead treats the signature tensor as an element of the congruence orbit of a fixed core tensor C, and reduces it to C by a sequence of upper, lower, and diagonal Gauss transformations. The upper transformations are found by solving a linear system, not a polynomial one; a randomized coordinate change sidesteps rare degenerate cases. The result is an expected O(d^4) algorithm with a 100% success rate by design, replacing the previous approach by an order of magnitude.","feed_headline":"Path recovery from signature tensors drops to O(d^4)","feed_subtitle":"An exact Gauss-type reduction replaces Gröbner bases for third-order signature inversion in any dimension.","key_machinery":"The central object is the matrix-tensor congruence action A*C with entries (A*C)_{ijk} = Σ C_{αβγ} A_{iα} A_{jβ} A_{kγ}, and the fixed upper-triangular core tensor C_{ijk} equal to 1, 3, or 6 according to whether i=j=k, i=j<k or i<j=k, or i<j<k. The mechanism that carries the argument is the Gauss-transform ladder: upper transforms U(s,x) (transposes of lower ones) are used to impose symmetry conditions on the tensor, lower transforms L(s,y) and diagonal scalings D(s,h) then eliminate the newly symmetric entries, reducing the problem to a smaller congruence orbit. The load-bearing identity is Lemma 5.5, which expresses the effect of an upper transform on the difference H_{ijs} - H_{jis} as a","core_discovery":"The central claim is Theorem 1.1: for every d×d×d tensor G in the orbit GL_d * C of the core tensor C (the third-level signature of the canonical axis path), Algorithm 1 computes an invertible matrix A with G = A*C, using O(d^4) elementary operations in expectation. The proof works by iterating s = 1,...,d-1: at each step an upper Gauss transform (computed from a linear system Mx = B built from entries of G) puts the tensor into a normal form satisfying the four conditions of Theorem 3.2; lower and diagonal transforms then move the tensor into the smaller orbit (I_s ⊕ GL_{d-s}) * C. The recursion terminates at the core tensor, and uniqueness of the solution (the trivial stabilizer of C) turn","pith_inferences":["If the O(d^4) bound holds in practice, signature inversion becomes feasible in dimensions of order tens to hundreds, opening the door to using third-level signatures as a practical data representation in machine learning pipelines, where current methods stop near d=10.","The same Gauss-normal-form strategy might apply to higher-order signature tensors or to other congruence orbits of tensors with a trivial stabilizer, though the low-dimensional exceptional cases (d=2,3) suggest that each order may need its own special handling.","Because the reduction is rational (the core tensor is rational and the transformations are rational), the algorithm constructs the path matrix over the rationals; this means it could be used to certify exact recovery in symbolic computation, not just floating point.","The linear-system formulation suggests that the computational bottleneck is a structured (d-s)^2 × (d-s) linear solve at each step, so highly optimized solvers could push the practical dimension higher than the reported table."],"forward_implications":["The third-order signature inversion problem in dimension d is solvable exactly in expected O(d^4) operations, replacing the previous Gröbner-basis approach whose cost grows far faster.","Every tensor in the congruence orbit of the core tensor C can be normalized to C by congruence Gauss transformations, giving a constructive normal form for this third-order tensor congruence action.","The recovery is exact and unique: the returned matrix A satisfies G = A*C, and no other matrix does, because the stabilizer of C is trivial.","The algorithm's randomization ensures a 100% success rate in expectation: degenerate cases are escaped by random coordinate changes rather than by solving hard polynomial systems.","The method extends the trivial-stabilizer theorem to partial orbits: if a tensor agrees with C on a certain index pattern, it already lies in (I_s ⊕ GL_{d-s})*C, enabling the recursive step."],"fun_headline_variants":["Exact path recovery from signature tensors in O(d^4)","O(d^4) algorithm recovers paths from signature tensors","Signature tensor inversion: exact and O(d^4) now","From signature to path: O(d^4) exact algorithm"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The algorithm's correctness depends on a random coordinate change landing on a generic tensor where the linear system Mx = B has full rank; if degenerate tensors occurred with positive probability — or if the core tensor had a nontrivial stabilizer — the recursive reduction could either loop forever or recover the wrong matrix.","fun_headline_variants_meta":{"raw":{"variants":["Exact path recovery from signature tensors in O(d^4)","O(d^4) algorithm recovers paths from signature tensors","Signature tensor inversion: exact and O(d^4) now","From signature to path: O(d^4) exact algorithm"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000538,"raw_usage":{"total_tokens":2359,"prompt_tokens":621,"completion_tokens":1738,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":365,"completion_tokens_details":{"reasoning_tokens":1665}},"tokens_in":365,"tokens_out":1738,"duration_ms":12021,"temperature":1.0,"reasoning_tokens":1665,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T16:12:17.014822+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit a tensor G = A*C for which the matrix M from Algorithm 2 becomes rank-deficient for every random coordinate change W, forcing the recursion to loop without terminating; or exhibit a non-identity A with A*C = C, contradicting the trivial-stabilizer theorem.","supporting_citations":[],"review_version":1}