Pith. sign in

REVIEW 3 major objections 7 minor 29 references

Fast Capture of Cell-Level Provenance in Numpy

T0 review · 3 major / 7 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Cell-level provenance in numpy becomes practical when annotations are stored in preallocated C buffers, cutting annotation latency by up to 275x for element-wise and 34000x for aggregate operations.

desk verdict Plausible memory-management speedups for numpy provenance capture, but the two-primitive coverage claim is internally contradicted by the paper's own np.where example. read the letter →

arxiv 2506.18255 v1 pith:XVJ3IUU7 submitted 2025-06-23 cs.DB

Jinjin Zhao , Sanjay Krishnan This is my paper
classification cs.DB
keywords cell-levelprovenancenumpylineagetrackingarrayworkflowsannotationmemoryoptimizationdatagovernancetracked_float
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper argues that the main obstacle to cell-level provenance capture in numpy is memory management, not semantics. The authors present a prototype in which each array cell carries a provenance list—a C array of integer triples identifying input cells—and every numpy operation is handled by just two primitives: copying provenance for unary operations and concatenating the two input lists for binary operations, with the output provenance being the union of the input parents. By preallocating buffers for these lists, the prototype reports annotation latency up to 275 times lower than a naive Python implementation for element-wise operations and up to 34,000 times lower for aggregates, while staying within about 5x and 44x of bare numpy on arrays with up to 100 million cells. If these numbers hold, real-time cell-level provenance becomes feasible for large array workflows, which would support reproducibility, governance, and data-quality guarantees in data science pipelines.

What carries the argument

The central object is `tracked_float`, a C-backed numpy scalar type whose value is a float and whose provenance is a C array of 32-bit integer triples: one field for the source array ID and two for cell indices. The first triple is embedded directly in the annotated cell, and later triples live in a dynamically allocated buffer that can be preallocated for known operations. The argument runs on the fact that any numpy operation only needs two provenance primitives—copy the input's provenance for unary operations, concatenate the two inputs' provenance for binary operations—and that preallocation eliminates the repeated memory reallocation that dominates naive annotation.

What would settle it

Run a masked reduction on a $10^{8}$-cell tracked_float array and compare each output cell's recorded parent set with the cells that actually contribute under numpy's semantics; a mismatch would show the union-of-parents model is not equivalent to true cell-level lineage. Separately, rerunning the paper's aggregate microbenchmark at $10^{8}$ cells should reproduce an annotation overhead near 44x bare numpy and under roughly 50 seconds; a dramatically larger overhead would falsify the performance claim.

Watch

Extended reading notes

Core claim

The paper's central claim is that cell-level provenance capture over numpy can be made fast enough for large arrays by concentrating on how provenance lists are stored. In the prototype, each cell's lineage is a C-level list of (array ID, row, column) triples, and annotation is reduced to copying that list for unary operations and concatenating lists for binary operations. The measured effect is that this design lowers annotation latency by up to 275x for element-wise operations and by up to 34000x for aggregate operations relative to a Python implementation of the same annotation behavior, while remaining within roughly 5x and 44x of unannotated numpy. The system scales to arrays of 100 million cells, with aggregate provenance capture adding under 50 seconds in the largest experiments. The paper presents this as evidence that real-time, API-robust provenance capture for array workflows is achievable with careful memory management.

Load-bearing premise

The load-bearing premise is that every numpy operation can be expressed as one of two primitives—unary copy or binary concatenation of parent lists—so that the union of input cell parents is the correct lineage for any operation.

Editorial extensions

If this is right

  • Array workflows can be annotated at cell granularity without rewriting user code; converting an ndarray to the tracked_float type and letting the two primitives run is enough for coverage.
  • The gap to bare numpy (roughly 5x element-wise, 44x aggregate) is small enough that provenance capture could be enabled by default in settings that require governance or reproducibility.
  • Because coverage follows from two primitives, supporting a new numpy operation only requires classifying it as unary or binary; API updates do not force provenance logic to be rewritten.
  • The captured annotations feed DSLog's existing compression and in-situ query processing, so users can explore lineage without materializing every parent list as a separate table.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The paper does not microbenchmark data-dependent operations such as element selection or masked reductions that decide output cells at runtime; whether union-of-parents remains complete for those operations is untested.
  • The same buffer-preallocation strategy should transfer to other array containers, such as dataframe columns or tensor libraries, because the two primitives are independent of numpy's internal dispatch; the paper gestures at universality but does not demonstrate it.
  • Duplicate annotations are permitted and deferred to post-processing; for aggregation-heavy workloads an online de-duplication scheme could trade a little memory for faster downstream querying, but the paper does not explore that trade.
  • The reported 34000x speedup depends on preallocating buffers for known aggregations; a natural extension would be to predict buffer sizes for arbitrary pipelines rather than relying on function-specific preallocation.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 7 minor

Summary. This paper presents a prototype for cell-level provenance capture in numpy, built as part of the DSLog system. The prototype uses a C-backed tracked_float data type that stores provenance tuples (array ID and cell indices) in a buffer, with the first tuple embedded inline and optional preallocation for known aggregate functions. The authors report microbenchmarks on arrays up to 100 million cells, comparing DSLog against a Python-implemented baseline and a C baseline without preallocation. They claim up to 275x speedup for element-wise operations and up to 34000x for aggregate operations over the Python baseline, with overhead within 5x and 44x of bare numpy respectively. The paper further claims that capturing provenance for all numpy operations reduces to two primitive data operations: unary copy and binary concatenation of provenance arrays, under a union-of-parents semantics.

Significance. If the performance results are reproducible, the memory-management engineering contributes a simple and plausible optimization: preallocating provenance buffers and embedding the first annotation inline can substantially reduce annotation overhead for element-wise and reduction workloads. The paper clearly describes the data structure and provides an ablation against two baselines, which is a strength. However, the manuscript's central generality claim, that two primitives cover all numpy operations, is contradicted by its own motivating example (np.where), and the correctness of the union-of-parents provenance semantics is never evaluated. The performance claims also lack experimental detail, including hardware, repetitions, variance, and code availability. As a short preliminary-experience paper, the latency results are suggestive but the scope of the claims exceeds the evidence.

major comments (3)
  1. [Section 2.2] The claim that 'To implement provenance capture for all numpy operations using this data structure, we only need to adjust two primitive data operations' is not supported and is internally contradicted by the motivating example in Section 1.1. The hotspots example uses np.where, a data-dependent, variable-cardinality operation: the number of outputs depends on runtime data, and each output's true lineage includes the condition cell(s) and the contributing input cells. A unary-copy/binary-concatenation scheme cannot select cells based on data, cannot emit a variable number of outputs, and does not record the condition cell as a dependency. The same gap affects np.sort, np.take, np.nonzero, and masked indexing. Section 3's measurements cover only element-wise (copy) and whole-axis reduction (concatenation) patterns, so the reported speedups do not establish that the prototype captures provenance for the full numpy API.
  2. [Sections 2.1-2.2] The union-of-parents semantics is presented as 'effectively capturing lineage information for all numpy operations,' but for selection-like operations it over-approximates true dependencies: an output produced by a filter would be recorded as depending on all input cells rather than only the selected value and condition. The paper never evaluates the correctness of the captured provenance (no comparison against expected lineage, no small worked examples beyond Figure 2), so it is unclear whether even the supported element-wise and reduction operations produce semantically correct cell-level lineage. Section 4's discussion of 'Partial Provenance' acknowledges that all-inputs-to-all-outputs is an assumption for black-box operations, but the current system is presented as exact for the full numpy API rather than as an approximation.
  3. [Section 3] The quantitative claims ('up to 275x', 'up to 34000x', overhead within 5x and 44x) are reported without the experimental conditions needed to interpret or reproduce them. No hardware description, numpy version, number of runs, or variance/error bars are given for Figures 4 and 5. The C baseline is described in Section 3 but omitted from Figure 5(A) with the statement that it is identical to DSLog, and its behavior in Figure 5(B) is not fully quantified. The paper should either report the raw data and full methodology or clearly frame the numbers as illustrative single-run results.
minor comments (7)
  1. [Abstract and Section 1] The sentence 'the core contribution of this paper is demonstrate that efficient memory management...' should read 'is to demonstrate that...'.
  2. [Section 2.1] The code snippet 'c.parents = [(c.index1, c.index1)]' appears to contain a typo; the surrounding text says the top-left cell is annotated with index (0,0), so the second element should presumably be a different coordinate (e.g., c.index2).
  3. [Figure 4] Figure 4 lacks axis labels and units; please specify what is being measured (e.g., time in seconds) and add a caption describing the setup.
  4. [Section 3.3] The statement 'adds less than 50 seconds of overhead' should specify the exact operation and array size (presumably the aggregate case at 100M cells) to be interpretable.
  5. [References] References [25] and [26] appear to be the same work (ICDE 2024 and an arXiv preprint) listed with different citation keys; please distinguish them or remove the duplicate.
  6. [Section 4] The phrase 'We forsee' should be 'We foresee'.
  7. [Section 6] The sentence 'We see as this early work towards...' is grammatically incomplete; please rephrase.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the latency results are external measurements, and the two-primitive provenance model is an explicit design choice rather than a prediction derived from fitted inputs.

full rationale

The paper's central performance claims (up to 275x and 34000x speedups over a Python baseline, with overhead of at most 5x and 44x versus bare numpy) are microbenchmark measurements in Section 3, comparing a C-backed tracked_float prototype against a Python baseline and a C baseline without preallocated buffers. No parameter is fitted to the measured data, and no measured quantity is reused to define the claimed result, so the speedups cannot reduce to their inputs by construction. The provenance semantics are explicitly defined in Section 2.1 as the union of input parent sets, and the two primitive operations in Section 2.2 (unary copy and binary concatenation of prov_id arrays) are a direct encoding of that stated semantics rather than an independent result derived from it. The DSLog self-citations provide background and the lineage model, but the benchmark comparisons do not depend on accepting those papers' results; the prototype's performance is evaluated directly. The generality of union-of-parents semantics to all numpy operations is a correctness or scope assumption, not circularity: the paper states that the prototype targets the union of input cell contributions, and the evaluation covers element-wise and aggregate patterns as stated extremes. No uniqueness theorem, fitted parameter, or hidden redefinition drives the central claims. Therefore, no circular step is present.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

No free parameters are fitted to data. The prototype's claims rest on three unstated assumptions about union semantics, API coverage by two primitives, and generalization to higher dimensions. The tracked_float data structure is an implementation artifact contributed by the paper, not an unexplained assumption or invented physical entity.

assumptions (3)
  • domain assumption Union of input parent lists is the correct cell-level provenance for all numpy operations.
    Introduced in Section 2.1 (c.parents = Union(a.parents, b.parents)) and used without proof across the API; duplicate annotations are allowed, implying non-union dependency patterns are ignored.
  • ad hoc to paper Two primitive operations (unary copy and binary concatenation) cover every numpy operation.
    Section 2.2 states this directly; no survey or proof of coverage is given, and benchmarks only test element-wise and aggregate shapes.
  • domain assumption Provenance tuples with one array ID and two indices generalize to higher-dimensional arrays.
    Section 2.2 says 'though this strategy generalizes to higher dimensions' but provides no implementation or test.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Fast Capture of Cell-Level Provenance in Numpy." pith.science (2026). https://pith.science/paper/XVJ3IUU7

@misc{pith2026250618255,
  author       = {Pith},
  title        = {Pith review of: Fast Capture of Cell-Level Provenance in Numpy},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XVJ3IUU7}},
  note         = {Machine review of arXiv:2506.18255}
}
read the original abstract

Effective provenance tracking enhances reproducibility, governance, and data quality in array workflows. However, significant challenges arise in capturing this provenance, including: (1) rapidly evolving APIs, (2) diverse operation types, and (3) large-scale datasets. To address these challenges, this paper presents a prototype annotation system designed for arrays, which captures cell-level provenance specifically within the numpy library. With this prototype, we explore straightforward memory optimizations that substantially reduce annotation latency. We envision this provenance capture approach for arrays as part of a broader governance system for tracking for structured data workflows and diverse data science applications.

Figures

Figures reproduced from arXiv: 2506.18255 by the authors.

Figure 1
Figure 1. Visual illustration of two non-standard array oper [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Example of provenance capture. whose intensities significantly surpass those of their neighbors, signaling potential areas of interest. This analysis can be represented through a simplified array-based pipeline: def hotspot ( X ) : X_smoothed = smooth ( X ) hotspots = where ( X_smoothed > 0.5) return hotspots Here, smooth(X) applies a smoothing filter (e.g., calculating mean intensity within a neighborhood), and whe… view at source ↗
Figure 3
Figure 3. Diagram of DSLog’s tracked_float memory struc [PITH_FULL_IMAGE:figures/full_fig_p003_3.png] view at source ↗
Figures from the paper (1 more)
Figure 5
Figure 5. Figure 5: Execution overhead of provenance annotation. [PITH_FULL_IMAGE:figures/full_fig_p004_5.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

29 extracted references · 24 canonical work pages

  1. [1]

    Bogdan Alexe, Laura Chiticariu, and Wang Chiew Tan. 2006. SPIDER: a schema mapPIng DEbuggeR. InVery Large Data Bases Conference. https: //api.semanticscholar.org/CorpusID:11896236

    work page 2006

  2. [2]

    Chapman, Paolo Missier, Giuliano Simonelli, and Riccardo Torlone

    Adriane P. Chapman, Paolo Missier, Giuliano Simonelli, and Riccardo Torlone

    work page

  3. [3]

    James Cheney, Laura Chiticariu, and Wang Chiew Tan. 2009. Provenance in Databases: Why, How, and Where.Found. Trends Databases1 (2009), 379–474. https://api.semanticscholar.org/CorpusID:1778556

    work page 2009

  4. [4]

    Laura Chiticariu, Wang Chiew Tan, and Gaurav Vijayvargiya. 2005. DBNotes: a post-it system for relational databases based on provenance. InACM SIGMOD Conference. https://api.semanticscholar.org/CorpusID:6489543

    work page 2005

  5. [5]

    Yingwei Cui and Jennifer Widom. 2000. Practical lineage tracing in data warehouses.Proceedings of 16th International Conference on Data Engineering (Cat. No.00CB37073)(2000), 367–378. https://api.semanticscholar.org/CorpusID: 15647832

    work page 2000

  6. [6]

    Stefan Grafberger, Julia Stoyanovich, and Sebastian Schelter. 2021. Lightweight Inspection of Data Preprocessing in Native Machine Learning Pipelines. InCon- ference on Innovative Data Systems Research. https://api.semanticscholar.org/ CorpusID:232203702

    work page 2021

  7. [7]

    Green, Grigoris Karvounarakis, and Val Tannen

    Todd J. Green, Grigoris Karvounarakis, and Val Tannen. 2007. Provenance semir- ings. InProceedings of the Twenty-Sixth ACM SIGMOD-SIGACT-SIGART Sympo- sium on Principles of Database Systems(Beijing, China)(PODS ’07). Association for Computing Machinery, New York, NY, USA, 31–40. doi:10.1145/1265530.1265535

    arXiv 2007

  8. [8]

    Harris, K

    Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Gérard-Marchant, Kevin Shepp...

    work page 2020

Show all 29 references
  1. [9]

    Thomas Heinis and Gustavo Alonso. 2008. Efficient lineage tracking for scientific workflows. InSIGMOD Conference. https://api.semanticscholar.org/CorpusID: 9728208

    2008

  2. [10]

    Millstein, and Tyson Condie

    Matteo Interlandi, Kshitij Shah, Sai Deep Tetali, Muhammad Ali Gulzar, Se- unghyun Yoo, Miryung Kim, Todd D. Millstein, and Tyson Condie. 2015. Titian: Data Provenance Support in Spark.Proceedings of the VLDB Endowment In- ternational Conference on Very Large Data Bases9 (2015...

    2015

  3. [11]

    Ives, Todd J

    Zachary G. Ives, Todd J. Green, Grigoris Karvounarakis, Nicholas E. Taylor, Val Tannen, Partha Pratim Talukdar, Marie Jacob, and Fernando Pereira. 2008. The ORCHESTRA Collaborative Data Sharing System.SIGMOD Rec.37, 3 (Sept. 2008), 26–32. doi:10.1145/1462571.1462577

    2008

  4. [12]

    Shachar Kaufman, Saharon Rosset, Claudia Perlich, and Ori Stitelman. 2012. Leakage in data mining: Formulation, detection, and avoidance. 6, 4, Article 15 (Dec. 2012), 21 pages. doi:10.1145/2382577.2382579

    2012

  5. [13]

    Paolo Missier, Khalid Belhajjame, Jun Zhao, Marco Roos, and Carole A. Goble

  6. [14]

    Mohammad Hossein Namaki, Avrilia Floratou, Fotis Psallidas, Subru Krishnan, Ashvin Agrawal, and Yinghui Wu. 2020. Vamsa: Tracking Provenance in Data Science Scripts.ArXivabs/2001.01861 (2020). https://api.semanticscholar.org/ CorpusID:210023441

    2020 arXiv

  7. [15]

    Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Des- maison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, L...

    2019

  8. [16]

    Ma, Doris Jung Lin Lee, Stephen Macke, Doris Xin, Xiangxi Mo, Joseph E

    Devin Petersohn, William W. Ma, Doris Jung Lin Lee, Stephen Macke, Doris Xin, Xiangxi Mo, Joseph E. Gonzalez, Joseph M. Hellerstein, Anthony D. Joseph, and Aditya G. Parameswaran. 2020. Towards Scalable Dataframe Systems.CoRR abs/2001.00888 (2020). arXiv:2001.00888 http://arxi...

    2020 arXiv

  9. [17]

    Pina, Adriane P

    Débora B. Pina, Adriane P. Chapman, Daniel de Oliveira, and Marta Mattoso. 2023. Deep Learning Provenance Data Integration: a Practical Approach.Companion Proceedings of the ACM Web Conference 2023(2023). https://api.semanticscholar. org/CorpusID:258377574

    2023

  10. [18]

    Fotis Psallidas and Eugene Wu. 2018. Smoke: Fine-grained Lineage at Interactive Speed.Proc. VLDB Endow.11 (2018), 719–732. https://api.semanticscholar.org/ CorpusID:3591285

    2018

  11. [19]

    Manasi Vartak, Joana M. F. da Trindade, Samuel Madden, and Matei A. Zaharia

  12. [20]

    Wes McKinney. 2010. Data Structures for Statistical Computing in Python. In Proceedings of the 9th Python in Science Conference, Stéfan van der Walt and Jarrod Millman (Eds.). 56 – 61. doi:10.25080/Majora-92bf1922-00a

    2010 doi

  13. [21]

    Eugene Wu, Samuel Madden, and Michael Stonebraker. 2013. SubZero: A fine- grained lineage system for scientific databases.2013 IEEE 29th International Con- ference on Data Engineering (ICDE)(2013), 865–876. https://api.semanticscholar. org/CorpusID:11139063

    2013

  14. [22]

    Zhepeng Yan, Val Tannen, and Zachary G. Ives. 2016. Fine-grained Provenance for Linear Algebra Operators. InWorkshop on the Theory and Practice of Provenance. https://api.semanticscholar.org/CorpusID:14082705

    2016

  15. [23]

    Sparks, and Michael J

    Zhao Zhang, Evan R. Sparks, and Michael J. Franklin. 2017. Diagnosing Machine Learning Pipelines with Fine-grained Lineage.Proceedings of the 26th International Symposium on High-Performance Parallel and Distributed Computing(2017). https: //api.semanticscholar.org/CorpusID:66162

    2017

  16. [24]

    Jinjin Zhao, Avidgor Gal, and Sanjay Krishnan. 2024. A System for Quantifying Data Science Workflows with Fine-Grained Procedural Logging and a Pilot Study. arXiv:2405.17845 [cs.HC] https://arxiv.org/abs/2405.17845

    2024 arXiv

  17. [25]

    Jinjin Zhao and Sanjay Krishnan. 2024. Compression and In-Situ Query Pro- cessing for Fine-Grained Array Lineage. In40th IEEE International Conference on Data Engineering, ICDE 2024, Utrecht, The Netherlands, May 13-16, 2024. IEEE, 3654–3667. doi:10.1109/ICDE60146.2024.00281

    2024

  18. [26]

    Jinjin Zhao and Sanjay Krishnan. 2024. Compression and In-Situ Query Pro- cessing for Fine-Grained Array Lineage. arXiv:2405.17701 [cs.DB] https: //arxiv.org/abs/2405.17701

    2024 arXiv

  19. [2008]

    InInternational Provenance and Annotation Workshop

    Data Lineage Model for Taverna Workflows with Lightweight Annotation Requirements. InInternational Provenance and Annotation Workshop. https: //api.semanticscholar.org/CorpusID:17928481

  20. [2018]

    https://api.semanticscholar.org/CorpusID:13815684

    MISTIQUE: A System to Store and Query Model Intermediates for Model Diagnosis.Proceedings of the 2018 International Conference on Management of Data(2018). https://api.semanticscholar.org/CorpusID:13815684

    2018

  21. [2020]

    VLDB Endow.14 (2020), 507–520

    Capturing and querying fine-grained provenance of preprocessing pipelines in data science.Proc. VLDB Endow.14 (2020), 507–520. https://api.semanticscholar. org/CorpusID:231842112 Fast Capture of Cell-Level Provenance in Numpy PW ’25, June 27, 2025, Berlin, Germany

    2020

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.