CompProv Produces Machine Readable Graphs Encoding Microscopic Algebraic Provenance for Reproducible Computation

1 Introduction

• Current provenance frameworks track files, datasets, or pipeline stages, but omit the algebraic transformations connecting algorithm inputs to outputs.Undocumented substitutions, rounding errors, or missing intermediate values can then propagate without a recoverable trace.Source: §1 · p. 2
• Intermediate values can disappear during execution, making manual logging structurally unreliable and uncaptured variables permanently unrecoverable afterward.The paper links this gap to measurement dysfunction in manual recording and to values overwritten in registers or stack frames.Source: §1 · p. 2
• CompProv wraps numerical values in high-precision objects that record each algebraic transformation in a serializable, self-contained Calculation Provenance Graph.The graph encodes variables, operations, and dependencies; it supports deterministic replay and input substitution without disclosing domain logic, provided the CompProv runtime and wrapper classes are available.Source: §1 · p. 3
• Operation-triggered capture makes coverage a property of the wrapper type, while immutability keeps the graph acyclic and safe to persist and replay.The contributions also include a unified CPG format, replay and substitution mechanisms, and empirical validation across finance, metrology, and hydrology.Source: §1 · p. 4

2 Related Work

• Provenance approaches draw their stopping point at different levels, while database provenance formalisms were not designed for imperative numerical computation.The paper frames this as a gap between recording what a pipeline did and recording how a program computed a result.Source: §2 · p. 4

2.1 Coarse-Grained Lineage, Workflow, and Environment-Level Provenance

• Coarse-grained lineage trades internal detail for scale or portability, while ReproZip packages an environment for rerunning code rather than replaying recorded operations.Meta’s Unified Lineage System tracks data flow across graphs with billions of nodes, while workflow tools track files and configuration without changing computational modules.Source: §2.1 · p. 5

2.2 Fine-Grained and Operation-Level Provenance

• Fine-grained systems record function calls, dataset columns, or per-cell dependencies, but their records do not provide a serialized, replayable execution trace.noWorkflow records function activations, Vamsa traces source columns, and PROLIT can produce per-cell dependency graphs.Source: §2.2 · p. 6
• CompProv’s deterministic replay re-resolves recorded operations in a new environment, unlike replay systems that reproduce nondeterministic thread or system-call schedules.Tape-based automatic-differentiation engines are its closest architectural relatives because they also build operation-level graphs through operator overloading.Source: §2.2 · p. 6

2.3 Numerical Accuracy and Rounding-Error Diagnostics

• Numerical-diagnostic tools estimate round-off error or locate accuracy loss, whereas CompProv records whether a result’s derivation is auditable; the two address complementary questions.A CPG records executed operations and their order, not whether a different valid order would change the outcome.Source: §2.3 · p. 7
• No system in the comparison provides more than three of five desired properties; CompProv targets their combination by making metadata capture and persistence intrinsic to arithmetic.The properties are operation-level granularity, a persistent serializable artifact, deterministic replay, audit metadata per value, and decoupling from proprietary source.Source: §2.3 · pp. 7–8

• CompProv organizes intrinsic metadata capture into cooperative layers, with the context layer accumulating the graph as execution proceeds.Source: §3 · p. 8
• Immutable variable states and operations form DAG nodes whose directed edges encode calculation flow and whose immutability guarantees acyclicity.Source: §3 · p. 9
• Variable tracks provide origin, name, type, and extensible audit metadata, while operation tracks link inputs to results with replay-oriented metadata.Source: §3 · pp. 9–10
• A Snapshot serializes a descriptor, ordered variable records, and chronologically ordered operation records, preserving the data needed for replay.Replay rewraps variables and re-executes recorded operations in chronological order.Source: §3 · pp. 10–12
• For computations using custom types or operations, replay requires the corresponding wrapper classes and operation implementations in the replay environment.The Snapshot contains the computation data and metadata, but not those runtime components.Source: §3 · pp. 11–12
• Input substitution duplicates a Snapshot, replaces eligible input values, preserves the operations, and labels both individual updates and the resulting scenario.Source: §3 · pp. 13–14

4.1 Provenance in NAV Calculation

• 431,749.17 USD was reproduced as the portfolio NAV in a fresh environment by deterministic replay of a serialized CPG.The graph records operations from external-rate ingestion through conversion; substituting exchange rates while holding asset amounts fixed supports sensitivity analysis without changing source code.Source: §4.1 · pp. 16–18

4.2 Interferometric Gauge Block Calibration

• +2 nm was the calculated deviation from the nominal 7,000,000 nm gauge-block length, conditional on stated assumptions rather than an independent validation.Seven of 13 inputs were reconstructed, and fractional fringe order f was selected to match the reference length; input-uncertainty propagation was outside the demonstration’s scope.Source: §4.2 · pp. 18, 19, 21

4.3 Hydrological Models Evaluation

• 0.93911746 was the highest KGE, achieved by hydrological Case 03 among 12 evaluated simulations.The CPG captured the derivation of the KGE metrics, making the comparison traceable and reproducible.Source: §4.3 · pp. 22–23, Table 6 · p. 23

4.4 Complexity Analysis

• For acyclic algorithms, CPG construction has expected O(T(N)) time complexity; in the iterative π benchmark, fully unfolded tracking increased time overhead and graph memory with iteration count.The algorithm’s working memory was O(1), whereas its provenance artifact grew as O(N) because each iteration added immutable graph nodes.Source: §4.4 · pp. 23–25
• Subgraph folding records one fully granular loop-body template and stores only each later iteration’s input and output, reducing snapshot size and cumulative time overhead.An auditor can inspect a selected iteration by rerunning the deterministic, side-effect-free template with its recorded input and checking the output.Source: §4.4 · pp. 25–26
• The arcsin benchmark integrated a function with an integrable singularity but infinite variance, making it slower and noisier to converge than standard polynomial estimators.Its purpose was to test how increased per-iteration computational complexity affects tracing overhead and memory consumption.Source: §4.4 · p. 27
• The arcsin workload’s CPG memory growth per 1,000 operations nearly stabilized, with reduced normalized footprint attributed to using one input instead of two.The reported absolute memory footprint is a conservative upper bound because the benchmarks use descriptive identifiers and metadata; compact identifiers could lower it.Source: §4.4 · p. 28, Figure 11 · p. 29
• Median relative tracing overhead fell from 5.84× in the π benchmark to 2.13× for arcsin, while median absolute overhead stayed near 3.3 ms.Native execution time per 1,000 operations increased from 0.69 ms to 2.97 ms, while absolute tracing overhead shifted from 3.35 ms to 3.30 ms.Source: §4.4 · p. 28
• Native and CompProv-wrapped 4-thread runs achieved speedups of 2.47× and 2.39×, respectively, showing comparable parallel throughput for this workload.The result demonstrates scaling under the tested concurrency pattern, not formal verification of thread safety or reentrancy.Source: §4.4 · p. 28

5 Discussion

• Across three structurally dissimilar case studies, CompProv produced records complete enough to replay, audit, and substitute inputs.The studies were designed to test this capability across domains, not to push the framework to its limits.Source: §5 · p. 29
• Seven of thirteen inputs to the gauge-block calibration were unrecorded, and the hydrological benchmark omitted KGE values and their derivation.The hydrological result for Case 03 was KGE 0.939 after processing the remaining 11 simulations through snapshot duplication.Source: §5 · pp. 30–31
• Unlike a transient automatic-differentiation tape, a persisted CPG can support an audit years after the original computation.The gauge-block and hydrological cases expose undocumented inputs and derivations that file-, pipeline-, or environment-level systems were not designed to capture.Source: §5 · p. 31
• The NAV calculation replayed exactly at 431,749.17 USD, and input substitution supported historical scenario analysis without the original trading system.The CPG can be shared for mathematical verification without disclosing the proprietary source code.Source: §5 · pp. 31–32
• The demonstrated workflows are small, deterministic, and acyclic; large simulations face linear graph growth, execution overhead, and replay dependencies on CompProv and domain classes.The discussion also notes a Java implementation barrier and no mechanism for replaying nondeterministic operations when external values have changed.Source: §5 · p. 32

6.1 External Validity

• Cross-language portability remains untested, and highly complex simulations may strain graph parsing and data ingestion.The proposed mitigation for complex simulations is to partition them into discrete stages; C++ or Python portability remains an architectural expectation, not a demonstrated result.Source: §6.1 · pp. 32–33

6.2 Internal Validity

• Folding reduces median overhead to 5.84× for lightweight tasks and 2.13× for computationally intensive payloads, from a 10.44× peak median increase in unfolded atomic-operation tracing.These overhead measurements motivate the performance concern for performance-critical and HPC environments.Source: §6.2 · p. 33
• Folding omits intermediate local variables inside each pass; drill-down re-executes the preserved Template and depends on it being deterministic and free of external side effects.The study benchmarks met that condition, but it was not verified in general.Source: §6.2 · p. 33

6.3 Construct Validity

• The utility metrics may not fully capture challenges of analyzing massive CPGs; proposed future work includes fragmentation and advanced analytics.The stated aim is to keep the transparency-to-overhead ratio favorable for large-scale scientific applications.Source: §6.3 · p. 33

7 Conclusion

• Immutable, metadata-carrying numerical wrappers captured each algebraic operation and produced a serializable CPG.The framework addresses the absence of operation-level traceability in systems that record only files, datasets, or pipeline stages.Source: §7 · p. 33
• Deterministic replay reproduced each result exactly in a fresh environment, and CPG-based input substitution supported sensitivity analysis without exposing source code.The evaluation covered finance, metrology, and hydrology case studies.Source: §7 · pp. 33–34
• CPG memory grows linearly with recorded operations, while wrapping incurred up to a 2.16 × ±0.27× execution-time overhead despite folding-based mitigation.The originating algorithm's working memory remained constant.Source: §7 · p. 34
• The evaluation covered only small, deterministic, acyclic workloads, and current overhead constrains high-performance computing applications.Future work includes CPG fragmentation and compression, broader overhead measurements, and a cross-language implementation.Source: §7 · p. 34
• The framework decouples numerical audit from disclosure of proprietary business logic and from the survival of a particular software environment.The authors describe it as a foundation for treating numerical integrity as a verifiable property of computation.Source: §7 · p. 34

Declarations

• The work was supported by UAEU through the Program for Advanced Research under Grant 12N174, and the authors declared no competing interests.Source: Declarations · p. 34
• Study data are included in the article and supplementary files, and the CompProv framework and rendering engine are available in repositories.Supplementary spreadsheets include pi-estimation, arcsin-integration, sensitivity-analysis, and hydrological data.Source: Declarations · p. 34
• M.A. led the framework development and experiments, while M.A.A. and N.S. contributed conceptual development, supervision, validation, interpretation, and manuscript review.All authors approved the final manuscript.Source: Declarations · p. 35