The Streaming Engine

10.1 What one tick actually changes

A rolling window of w points advancing by one point shares w−1 points with its predecessor. Recomputing the signature from scratch reads all w of them; almost all of that work was done a tick ago and thrown away. §1.6 already says it does not have to be. Split the old window into its first increment and the rest, and the new window into that same rest and its final increment:

Chen's identity supplies the two products; the group structure supplies the inverse. Neither factor knows how long the window is — out is the increment leaving at the left end, in the one arriving at the right — so the cost of a tick is a function of depth and the channel count alone. That holds from the point where there is a departing increment, i.e. once the window is full; the warm-up before that is a separate question and §10.3 answers it. That is the whole of v0.3. Everything after this section is about whether the constant, the preprocessing and the floating-point arithmetic cooperate.

10.2 The inverse, twice

The truncated tensor algebra makes the inverse embarrassingly concrete. For an element a with scalar part 1, solving (a ⋅ a⁻¹)_k = 0 level by level gives

a triangular recursion that terminates at level depth. This is worth saying out loud because it is easy to assume otherwise: the inverse is not a series being truncated for convenience. Truncation happens once, when the algebra is chosen; inside it the inverse is exact, and tensor_inverse computes it in depth passes.

It also has a reading at the level of paths. The inverse of S(x) is the signature of x walked backwards, and coordinate by coordinate it is the Hopf-algebra antipode: the coefficient of a word w in S⁻¹ is (−1)^|w| times the coefficient of w reversed in S. Both statements are tests rather than remarks.

And then the practical joke: the hot path never runs that recursion. The departing piece of a sliding window is a single straight segment, whose signature is exp(v), and

— the path reading again, now doing work: to undo a straight segment, walk it backwards. streaming._block_inverse reverses the block and negates each vector, which is both cheaper than the recursion and better conditioned, since it never forms the large intermediate products the recursion does. The two are pinned against each other in the tests, so the shortcut cannot silently stop being the inverse. The general recursion is still what suffix_signature uses, where the departing piece is an arbitrary cached prefix rather than one segment.

10.3 Preprocessing arrives in blocks

The identity in §10.1 is about the raw window. rollsig's windows are not raw — the ORVP arm feeds a time-augmented, lead-lag embedded path, and the whole point of the library is that those defaults are the finance-facing part. So the question is whether preprocessing destroys the decomposition, and the answer is that it does not: each raw increment d maps to a fixed-size block of preprocessed increments, independent of everything else in the window.

plain      d  ->  [d]
time-aug   d  ->  [(d, dt)]
lead-lag   d  ->  [(d, 0), (0, d)]
both       d  ->  [(d, dt, 0, 0), (0, 0, d, dt)]

A block is one or two increments and never more, so sliding stays constant-size. This is the assumption the whole module rests on, and it is checked directly against preprocess_path rather than inferred — if the preprocessing ever stopped decomposing this way, every other test would still pass on the shared code path.

One consequence is easy to miss. time_augment spreads its channel over [0, 1] across however many points it is given, so dt = 1/(w−1) is a constant only once the window is full. While the window is still filling, every tick renormalises the time channel and thereby changes every increment already accumulated — the sliding identity simply does not apply to it. The engine recomputes during the fill and streams thereafter. That costs O(w²) once at the head of a stream, which amortises to nothing over a long one but is a real cost on short series and is worth naming rather than hiding.

10.4 Two options this implementation does not support

Worth being exact about the status of these two, because the temptation is to dress a scoping decision up as a theorem. Neither is impossible; both are unimplemented in v0.3, for reasons that say what implementing them would cost.

basepoint changes how the left boundary of the window is represented. It prepends the origin, so the path is 0, p₀, …, p_w−1 and its leading increment is p₀ itself. Slide by one and the leading increment becomes p₁ — not the old p₀ → p₁ increment. The new window is therefore not a sub-path of the old one, and the sliding identity as written has nothing to cancel. A streaming form exists — cancel the old leading increment and reinstate the new one, at the cost of roughly two extra multiplications per tick — and is not built here, because basepoint exists precisely to break the translation invariance the rest of this relies on, and the batch fallback is exact and cheap to reason about.

output="log_signature" is unsupported for a different reason: it returns coordinates in a backend's basis of the free Lie algebra (§6.2), while the streaming engine maintains the full tensor signature. Taking a log of the streamed tensor lands in canonical word coordinates, which are not the columns the batch route produces. Bridging the two means a basis conversion into whichever basis the configured backend uses — real work, and work whose failure mode is silent disagreement rather than an error, which is the exact thing §6.2 built a test to prevent. So it is left out, method="auto" falls back to batch, and method="streaming" raises rather than quietly returning different columns.

Both fall back to an exact batch computation, so neither is a correctness gap. They are performance gaps with a known shape, which is the honest way to describe them.

11.1 The constant that nearly ate the asymptotics

The first working version was correct, was flat in the window — and was slower than recomputing for any window under a couple of hundred points. It cost about 1,080 µs per tick, which is an absurd figure for arithmetic on a few hundred doubles.

The profile said the arithmetic was not the cost:

ncalls  tottime  function
 62000    0.689  numpy/lib/_shape_base_impl.py:1038(kron)
248000    0.505  numpy/lib/_shape_base_impl.py:513(expand_dims)
248000    0.391  numpy/_core/numeric.py:1426(normalize_axis_tuple)

62 np.kron calls per tick, and kron's own dispatch machinery — expand_dims, normalize_axis_tuple, reshapes — accounting for most of the time. np.kron is general over n-dimensional inputs. Every level here is one-dimensional, and for 1-D arrays the Kronecker product is just a flattened outer product:

np.multiply.outer(a, b).ravel()

Same numbers, about six times the throughput on this workload. It is a boring optimisation and it is the reason the chapter exists: the asymptotics were correct in the first version and completely irrelevant until the constant was dealt with. An O(1) update that costs a millisecond loses to an O(w) recompute for every window anyone actually uses.

11.2 Flat in the window

The claim under test is not "streaming is fast" but "streaming does not care how long the window is." One channel, time-augmented and lead-lagged — the configuration benchmarks/orvp feeds its signature arm — measured per tick in the steady state, after the window has filled:

Read the streaming column down: a hundred-and-twenty-fold change in window length moves it by a few percent, and what movement there is has no consistent sign. That is the theorem, measured. The recompute columns move by exactly the factor the window does, which is the other half of the same statement.

The auto refresh column is the default configuration, which re-anchors on a from-scratch recomputation once per window ticks (§12.2). One O(w) recompute per w ticks keeps the steady state O(1) amortised, and it shows up as a flat surcharge that also does not grow with the window.

11.3 The crossover, and who actually wins

Take the three comparisons in the order they deserve. Against RoughPy — the backend the library actually ships with — streaming wins at every window measured, from 1.7× at window 10 to 129× at window 1,200, and the ratio keeps climbing because one column is flat and the other is not. That is the number to quote. Against the numpy reference the ratio is bigger still (452×) and means less: both are interpreted, only one re-reads the window, and numpy is a test oracle rather than something anyone should compute features with. The real opponent is iisignature, which is compiled C, and there the honest answer is that streaming does not always win.

Depth 2: recomputing in C is faster out to window 600 (125 µs against streaming's 132) and loses by window 1,200 (231 against 135). Depth 3, where each recompute does more work: the crossover falls between 300 and 600 — at 300 iisignature wins 173 to 194, at 600 it loses 326 to 197.

Below the crossover, recomputing the whole window in C beats updating it in Python, asymptotics notwithstanding. This is not a defect to be apologised for; it is what the numbers say, and it is exactly the kind of claim that gets checked in an interview. What it changes is the code:

One thing the rule deliberately does not do is measure anything at fit time. It is a lookup on (backend, window, depth), so the same estimator always resolves to the same route, whatever machine or data it meets; method_ on the fitted estimator says which. The measurement behind it is at four preprocessed channels — ORVP's configuration — and a much wider path raises the streaming constant faster than the batch one, which is a limit of the calibration worth knowing before trusting auto there.

The other thing the table shows is where the ceiling is. The streaming update is dozens of small numpy calls, each with a fixed interpreter overhead of a microsecond or two, and that overhead is essentially the entire cost. A compiled implementation of the same identity would move the crossover to a very small window. That is a natural next step and it is deliberately not taken here: the point of this module is that the algebra is legible, and rollsig's stated non-goal is reimplementing low-level signature computation.

11.4 A retraction: §9.1's nested-window plan

Part II closed by handing v0.3 a concrete target. Each ORVP segment needs signatures over its last 600, 300 and 150 seconds; the 150-point path is a suffix of the 300-point path, which is a suffix of the 600-point one, so the naive route walks 1,050 points where 600 exist. §9.1 proposed recovering the suffixes by left-multiplying the full window's signature by the inverse of the departing prefix.

So the group inverse is the wrong tool for a nested family, and the reason is worth stating because it says where it is the right tool. A nested family can be re-decomposed — the windows share a fixed suffix and you get to choose the cut points. A sliding window cannot: it changes at both ends every tick, so there is no static decomposition to exploit and cancelling the departing end is the only route.

nested_suffix_signatures implements the chunked version, including the wrinkle that makes it non-trivial: time_augment normalises its channel per window, so a 150-point window's time channel runs at a different rate than the same stretch seen inside a 600-point one. The two differ by a dilation of one channel, and scaling a path channel acts on the signature diagonally — the coefficient of a word picks up the scale factor once per occurrence of that letter. So the fix-up is algebra.dilate, not a recomputation.

And then the measurement, which is where the second half of the retraction lives:

The chunked route does save what the point count says it should: 46.4 ms per segment against the naive numpy route's 76.7, a 1.65× improvement where 1,050/600 = 1.75× is the ceiling, the gap being the extra tensor multiplications that stitch the chunks together. And then the number that settles it — calling iisignature three times does the whole job in 0.58 ms, eighty times faster than either numpy route. For ORVP's feature build the correct answer is to call the compiled backend three times and not be clever. The chunked route is worth having when the backend is the numpy one, and would be worth having again if the algebra were ever compiled; neither is where this benchmark sits, and saying so is cheaper than discovering it later.

12.1 What accumulates, and along which axis

§9.1 flagged this before any of the code existed: repeated multiplication by group inverses compounds floating-point error in a way recomputation does not, and the higher levels are where the coefficients are smallest. That guess was right about the mechanism and understated the size of it.

Measured as an infinity-norm ratio against a from-scratch signature of the same window — absolute error alone is meaningless here, since a path with large total variation has a large signature and both grow together:

Two things stand out. Depth is the axis that matters: three orders of magnitude of drift for every extra level, from machine precision at depth 2 to 10⁻⁹ at depth 5. And the growth in time is quadratic, not the square root a random walk of rounding errors would give — doubling the number of unanchored ticks multiplies the drift by about four, consistently, from 4.4×10⁻¹³ at 2,500 ticks to 1.7×10⁻¹⁰ at 40,000. Drift is therefore not something a long-running stream grows out of.

The axis that matters is depth, and steeply. That is mechanical rather than mysterious: level k of a product is a sum over all the ways to split k, so its rounding error is fed by every level beneath it, and it is simultaneously the level whose own coordinates are smallest. Error flows upward and the denominator shrinks.

The path's own scale is a second-order effect by comparison, and not even a monotone one. Sweeping the increment standard deviation over four orders of magnitude — 10⁻⁴ to 1 — moves the depth-4 drift between 4×10⁻¹¹ and 1×10⁻⁹ and then back down to 6×10⁻¹² at the largest scale, because once the price channel dominates the augmented time channel the signature's own magnitude grows faster than the error does and the ratio improves. Two orders of magnitude of variation, against seven for depth. The conditioning story is about the algebra, not about the data.

12.2 Re-anchoring, for free

The fix is the obvious one and the accounting is what makes it worth doing. Every w ticks, throw the accumulated element away and recompute the window from scratch. One O(w) recomputation per w ticks keeps the steady state O(1) amortised — the asymptotic claim survives, with that word attached — and no error can survive longer than one window's worth of updates.

Measured, that is a 23–37% surcharge per tick, flat in the window (the + auto refresh column in §11.2), and it takes the drift to 7×10⁻¹⁵ at every depth from 2 to 5 — four orders of magnitude better at depth 4, six at depth 5. The residual is the recomputation's own rounding, which is the floor any implementation has.

That is why refresh_every="auto" is the default rather than an option for the cautious. A library whose headline feature silently degrades at high depth over a long stream would be a bad library; one that costs a measured surcharge and stays at machine precision is a usable one. refresh_every=None exists so the benchmark can measure the drift in the raw, and is the wrong choice for anything else.

12.3 Where v0.3 stands

Shipped: rollsig.algebra, the truncated tensor algebra as an object you can call — multiply, inverse, exp, log, dilate — with the group laws as property-based tests rather than comments; and rollsig.streaming, which turns it into StreamingSignature, rolling_signature, suffix_signature and nested_suffix_signatures. SignatureTransformer gained method, and for plain signature output against the default backend it resolves to streaming, which means the v0.1 test suite has been re-running the v0.3 code path from the moment it was wired in.

Not shipped, and scoped out rather than overlooked: streaming log-signatures (§10.4), streaming with a basepoint (§10.4), a constant-time warm-up under time augmentation (§10.3), and a compiled implementation (§11.3). Each has a route; none is built.

The claim v0.3 supports, stated as narrowly as it deserves: the group structure of the tensor algebra makes a rolling signature cost O(1) per tick in the steady state — O(1) amortised with re-anchoring on, and after an O(w) warm-up under time augmentation — instead of O(window) forever; the flatness is measured rather than asserted, and so is the 129× it buys over the default backend at window 1,200 and the crossover below which a compiled backend still wins; the numerical price is quantified and bounded; and one prediction the project made about itself in v0.2 turned out to be wrong and has been retracted rather than quietly dropped.