{"id":"b51543fa-b860-4a66-8a2d-4975f128cfe8","arxiv_id":"2506.18252","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"XProv is a proposed architecture that uses lineage-constraint tags and small-sample learning to capture cross-library data lineage with uncertainty.","lead":"This vision paper proposes XProv, a system that would track how data moves across different programming libraries in one common format. It also sketches how an AI could learn that data movement for unfamiliar functions by testing small data samples.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The small-container learning method cannot discover value-triggered lineage (e.g., dropna row deletion) when the triggering value is absent from the sampled input domain; the motivating example is unverified.","rationale":"The reader's weakest assumption is that lineage learned on small examples generalizes to larger inputs. I agree that scale-invariance is unvalidated, but I identify a more specific and more immediate failure: the proposed perturbation strategy is restricted to the observed domain of the sampled container, so value-triggered behaviors (such as NULL-induced row deletion in dropna) can be completely invisible in the learning examples. This is not a matter of extrapolating from small to large; the learned tag can be wrong even for the exact container from which the small examples were drawn, if the trigger value is absent from the subsample. The paper's own dropna example makes this concrete: the indirect influence of all cells in a row depends on the presence of NULL, which the domain-preserving perturbation scheme may never test. This concern is load-bearing because the entire proposed approach to unknown operations rests on the sufficiency of the small-example perturbation set. I still view the paper as a vision paper that is honest about its status, so CONDITIONAL remains the right verdict; my read does not change the reader's assessment. A single targeted experiment on dropna would settle whether the proposed algorithm can recover even its own headline example.","tokens_in":11329,"tokens_out":6344,"duration_ms":79203,"concrete_test":"Run the Section 3.1 algorithm on pandas.DataFrame.dropna using an initial input container whose subsampled indices contain no NULL values (while the full container has at least one NaN in an unsampled row). If the learned tags do not include Slice/Condition or other row-deletion dependencies, the algorithm fails the paper's own motivating example and the central claim remains unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 3.1's proposed algorithm restricts perturbations to the domain of the initial container: steps (1) and (2) are 'necessary so that the domain of the elements from the initial container is preserved.' For value-dependent operations like the paper's own pandas.dropna example (Section 2.3), the row-deletion lineage is triggered by a NULL/missing marker. If the subset of indices sampled in step (2) contains no NULL, then NULL is outside the perturbable domain, so no perturbation can ever change whether a row appears in the output. The operation will appear to be Identity/One-to-One on all small examples, and the learned lineage constraint will miss the true Slice/Condition behavior. Thus the claim that 'there would exist some perturbation that would affect all indirectly influenced output elements' (Section 3.1) fails even for same-size inputs; this is not merely a scale-invariance issue. Since this perturbation-based small-example capture is the only concrete mechanism proposed for unknown operations, the central promise—lineage capture without intermediate data states—is not established for common value-dependent operations. The paper explicitly defers evaluation (Section 4.1), but the algorithm has a specific, fixable blind spot that directly undermines the motivating example.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This vision paper proposes XProv, an architecture for cross-library data lineage in data science workflows. XProv represents all significant data as multidimensional arrays (data containers), materializes low-level lineage graphs, and augments them with human-defined or learned 'lineage-constraint tags' such as One-to-One, Slice, and Condition. For unknown operations, Section 3 proposes to learn these tags by executing the operation on small perturbed containers derived from a recorded input, then generalizing the learned pattern to full-size inputs. The paper also sketches applications to information-leakage detection and operation reordering, and reports anecdotal LLM experiments. There is no implementation or empirical evaluation; the paper explicitly states that evaluation is future work.","tokens_in":11558,"tokens_out":8655,"duration_ms":81873,"significance":"The core idea of a parameterized, cross-library provenance IR with a tunable uncertainty-capture trade-off is timely and could be a useful organizing concept for the provenance community. The paper gives explicit definitions for influence lineage and constraint tags, connects the proposal to verified lifting and prior provenance systems, and is honest about its limitations (no evaluation, 2023 draft). However, the central learnability claim rests on a single unvalidated mechanism in Section 3.1, and that mechanism has a concrete blind spot for value-triggered operations such as the paper's own dropna example. The contribution is therefore conditional on fixing the learning algorithm and on at least a small proof-of-concept evaluation.","major_comments":[{"comment":"The perturbation-based algorithm cannot learn value-triggered lineage for operations where output membership depends on a value that does not occur in the sampled subcontainer. In the paper's own motivating example, pandas.dropna deletes a row when any element in that row is NULL (Section 2.3). Steps (1) and (2) deliberately preserve the domain of elements from the initial container, and step (3) perturbs only individual elements within that domain. If the subset of indices chosen in step (2) contains no NULL values, then no perturbation can create a row-deletion event, so the learned lineage is Identity/One-to-One rather than Slice/Condition. This contradicts the claim in Section 3.1 that 'there would exist some perturbation that would affect all indirectly influenced output elements': for the row-deleting entity, no such perturbation exists inside the permitted domain. Because this small-example probing is the only concrete mechanism proposed for black-box lineage capture, the Section 1 promise of capturing lineage 'without exposure to any intermediate data states' is not established for standard value-dependent operations. The algorithm should be extended to allow perturbations outside the observed domain (e.g., sentinel values such as NULL), or the scope of the learned-capture claim must be narrowed accordingly.","section":"§3.1 (steps 1–3) and §2.3"},{"comment":"The generalization assumption from small example inputs to full-size input containers is explicitly acknowledged but unvalidated, and it is load-bearing: if operations have scale-dependent code paths, data-dependent short-circuiting, or nondeterminism, tags learned on small containers will be wrong on production inputs. This is not a flaw by itself in a vision paper, but the claim that 'lineage from small example inputs can generalize to larger inputs' requires at least a concrete falsifiable evaluation plan (e.g., comparing learned tags against known ground-truth lineage for operations like filter, sort, and dropna across container sizes). Without this, the paper's central promise of capturing lineage for unknown operations is a plausibility argument rather than a supported design.","section":"§3.1 and §4.1"},{"comment":"The formal basis for the learning claim is under-specified: the domain A of possible values for A[a] is never defined. If A is the set of values occurring in the container, then value-triggered indirect influence is undetectable by definition; if A is the full domain of the data type, the step (3) perturbation procedure does not sample from it. Moreover, the phrase 'Under the assumption that the set {A} has a size of 1' (Section 3.1) is unclear because {A} is defined per output index in Section 2.3 and does not have an obvious global analogue. The learnability argument should either be restated in terms of explicit sampling distributions and coverage assumptions, or reframed as an open problem with a precise formal statement.","section":"§2.3 and §3.1"}],"minor_comments":[{"comment":"The pseudocode in Algorithm 1 contains confusing negations: `d ← !assert_tag(nop_sig, 'Slice', n.DIM)` appears to negate the slice assertion, and then `|d| != 0` is used as if `d` were a set of valid dimensions; similarly, `double_slice` uses `d` both as a boolean-like result and as the dimension parameter in the second assertion. The `row_wise` procedure adds nodes that are *not* Slice[0], which contradicts the text's description of ensuring row-wise operations. Please clarify whether `!` is a typo and define the return type of `assert_tag`.","section":"Algorithm 1"},{"comment":"The definitions of One-to-One, Identity, Slice, and Condition in Table 1 are not mutually exclusive and are too informal to serve as assertion functions; for example, One-to-One and Identity both relate each output entity to one input entity, and Slice[DIM] as defined would also cover Identity when DIM has size 1. Since the tags are the system's core IR, formal semantics (or at least a precise statement of intended non-exclusivity) would strengthen the proposal.","section":"Table 1 and §2.4"},{"comment":"The LLM experiments are reported without methodology: no prompts, no dataset, no number of trials, and no model version beyond 'GPT-3.5'. They are better framed as motivating anecdotes or moved to future work.","section":"§4.5"},{"comment":"The manuscript has many typos and template artifacts, including 'XProv all significant data' (§2.1), 'linage' (Table 1), 'back-box' (§3.1), incorrect CCS Concepts from a different template, and a 2018 ACM reference-format placeholder. A careful proofread is needed.","section":"Global"}],"recommendation":"major_revision","confidential_remarks":"To the editor: this is a vision/position paper with no implementation, and the Section 3.1 learning algorithm has a concrete blind spot on the motivating dropna example. I believe this is repairable within the scope of a vision paper: the author should either fix the perturbation scheme to include out-of-domain sentinel values and explicitly discuss coverage assumptions, or weaken the central claim. The paper is not ready for acceptance as is, but it contains useful ideas for the provenance community."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThis is a genuine vision paper: the idea of a lineage IR with constraint tags for cross-library data science workflows is new in the curated systems space, and the paper is honest about being a proposal. If you want to see what a community-discussion piece on provenance with uncertainty looks like, this is a reasonable example.\n\nWhat's actually new: the array-based IR with lineage-constraint tags, the plan to link materialized lineage graphs with abstract tags, and the sketch of learning tags from small perturbed containers. The two applications (leakage detection and reordering) are concrete enough to anchor the vision. The paper also scopes itself well, admitting that direct/indirect influence is known and that the system design is early.\n\nWhere it gets soft: the learning algorithm in Section 3.1 has a real blind spot, and it is not just about scale. The method restricts perturbations to values that appear in the sampled subset of the original container. For value-triggered operations like the paper's own pandas.dropna example, if the sampled subset contains no NULL, then no perturbation can ever change whether a row is deleted. The operation will look like Identity on those examples, and the learned tag will miss the Slice/Condition behavior. That means the motivating example fails for a common class of operations, even on same-size inputs. The paper does not address this. It is fixable (e.g., probe with sentinel values outside the observed domain), but as written it is a load-bearing gap in the only concrete mechanism proposed.\n\nOther weaknesses are expected for a vision: no implementation, anecdotal LLM tests, unverified generalization from small to large containers. The paper mostly acknowledges these. The citation pattern looks fine; the DSLog self-citation is used as a storage format and does not load the argument.\n\nWho should read it: people working on provenance for data science, especially cross-framework, will get value from the framing and the tag concept. It is not a systems paper yet, and the learning claim needs a demonstration. I would bring it to a reading group, but I would pair it with a critical discussion of the perturbation domain issue.\n\nVerdict: it deserves a serious referee as a vision paper, but the referee should push on the learning mechanism before acceptance. As it stands, it needs revision to address the dropna-class problem and to state clearly when the learning assumption holds.","headline":"A well-scoped vision for cross-library lineage with a novel tag-based IR, but the small-container learning mechanism has a real blind spot for value-triggered operations like the paper's own dropna example.","tokens_in":12107,"tokens_out":2807,"would_cite":true,"duration_ms":31836,"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":"This vision paper proposes that data lineage for unknown, black-box operations can be learned from small perturbed examples, without ever seeing intermediate data states.","keywords":["data lineage","provenance","cross-library workflows","intermediate representation","lineage-constraint tags","black-box operation learning","information leakage detection","query rewrite"],"falsifier":"Take a real data-science operation whose implementation is size-dependent (for example, a library routine that switches to a parallel or blocked algorithm above a certain container size, or one with random tie-breaking), run the paper's small-container perturbation procedure on it, and compare the learned lineage with the lineage obtained by instrumenting the implementation on a large input. If the predictions diverge on any operation, the proposed small-to-large generalization is falsified.","tokens_in":11088,"feed_emoji":"🔗","tokens_out":5334,"duration_ms":53941,"temperature":0.7,"pith_summary":"Data science workflows mix libraries with different data models, so lineage—which input elements produced a given output element—typically stops at library boundaries. This vision paper proposes XProv, a system that captures lineage across those boundaries by reducing all data to multidimensional arrays and annotating each operation with lineage-constraint tags that assert what kind of influence the operation can create. The central claim is that for operations never seen before, these tags and their lineage tables can be learned by probing the operation with small, perturbed example containers, without seeing internal data states or the underlying implementation. If the claim holds, lineage queries that today require either coarse dataset-level tracking or expensive memory-level instrumentation become possible across any library, enabling applications such as leakage detection and execution reordering.","feed_headline":"Cross-library lineage can be learned, not instrumented","feed_subtitle":"XProv vision: tags over arrays capture unknown operations' data influence for leakage and reorder queries.","key_machinery":"The load-bearing objects are the lineage-constraint tags: named assertions parameterized by dimension or index, each with an assertion function that validates whether a lineage instance matches, and an optional maximum constraint function that returns the most permissive lineage table consistent with the tag. They sit on top of a unified data model of multidimensional arrays with ordered indices, and below them are materialized influence-lineage tables stored relationally. The learning algorithm is the other main mechanism: it constructs small containers by taking index subsets, perturbs individual elements in the style of the direct and indirect influence definitions, re-runs the operation signature, and then relies on a machine-learning model (envisioned as few-shot) to choose the tags that fit all examples. The tags and their max-constraint functions then approximate the black-box operation's lineage.","core_discovery":"XProv's central proposal is that logical lineage in a cross-library workflow can be represented as a combination of materialized lineage graphs and abstracted lineage-constraint tags, each tag being an assertion over the operation's lineage and its input and output containers (for example, One-to-One, Slice[DIM], Identity, Conditional[DIM, INDEX]). A tag maps to an operation signature if and only if every possible node signature containing that operation signature satisfies the tag. For unknown operations, the paper argues that lineage can be learnt: by taking a subset of indices of an intermediate container, perturbing random individual elements, applying the operation signature to those small containers, and observing outputs, a downstream model can infer which tags hold and, via each tag's maximum constraint function, approximate the lineage as the intersection of all valid tag constraints. The paper states that in this manner lineage can be captured without exposure to any intermediate data states and without the underlying modifying structure, trading guaranteed correctness for tunable uncertainty.","pith_inferences":["The assumption that small-container patterns generalize to full-size inputs is untested in the paper; if real operations have size-dependent code paths (for example, switching to a parallel algorithm over a threshold) or hidden nondeterminism, learned tags will mislead. A natural first experiment is to test known library operations with such behavior.","The intersection-of-maximum-constraints idea could be carried further: instead of returning a single set of tags, a learner could output a distribution over tags, letting downstream applications weigh the risk of wrong lineage against task tolerance.","The same intermediate representation could double as a data-validation layer: lineage-constraint tags resemble data contracts, so learned tags might also serve as automatically inferred schema or quality contracts for data pipelines.","The paper's early LLM experiments suggest a testable extension: use LLM-generated hypotheses as candidate lineage tags for the learning step, rather than only human-authored tags, and verify them against the small-container probes."],"forward_implications":["If lineage-constraint tags can be learned for unknown operations, cross-library queries that were previously impossible become answerable—for example, asking whether an operation is a Slice[0] (row-wise) to detect leakage before a train/test split.","Applications such as rule-based execution reordering become feasible: a downstream tool can assert that two adjacent operations both slice on the same dimension and that the first is Identity, and safely switch their order.","Storing tags rather than full lineage tables offers compression and faster assertions, since queries can first search the knowledge base and only fall back to lineage tables when needed.","Provenance systems would no longer need to choose between dataset-level tracking and heavy memory-level instrumentation; a middle tier with tunable uncertainty becomes available.","Learnt lineage could be accepted for low-risk tasks like leakage inspection while exact lineage is still required for correctness-sensitive reordering, with the origin log letting users calibrate that risk."],"supporting_citations":[{"why":"Motivates the whole IR architecture by showing how a common intermediate representation enables cross-library optimizations.","marker":"[22]"},{"why":"Provides the 'verified lifting' analogy: translating low-level operations into a platform-agnostic higher-level representation.","marker":"[5]"},{"why":"Defines why-provenance and witness-set variations on which the direct and indirect influence lineage definitions are built.","marker":"[4]"},{"why":"Shows algebraic semiring structures for relational provenance, which lineage-constraint tags generalize beyond.","marker":"[10]"},{"why":"Represents the low-level Python variable tracking baseline that XProv augments with higher-level semantics.","marker":"[16]"},{"why":"A fine-grained lineage baseline that motivates the need for interactive-speed lineage with richer semantics.","marker":"[26]"},{"why":"Supplies the compression and in-situ query techniques used to store the relational influence-lineage tables.","marker":"[37]"}],"fun_headline_variants":["Learn cross-library lineage without instrumenting code","XProv: learn lineage from data, not code analysis","Lineage inference from data perturbations alone","Tag-based lineage for unknown cross-library ops","Learn lineage constraints, no instrumentation needed"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The method assumes that the lineage patterns observed on small, perturbed example containers match the lineage that the same operation produces on full-size input containers; if a real operation takes different code paths or behaves nondeterministically on larger data, the learned tags will be wrong.","fun_headline_variants_meta":{"raw":{"variants":["Learn cross-library lineage without instrumenting code","XProv: learn lineage from data, not code analysis","Lineage inference from data perturbations alone","Tag-based lineage for unknown cross-library ops","Learn lineage constraints, no instrumentation needed"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000615,"raw_usage":{"total_tokens":2815,"prompt_tokens":858,"completion_tokens":1957,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":474,"completion_tokens_details":{"reasoning_tokens":1890}},"tokens_in":474,"tokens_out":1957,"duration_ms":13732,"temperature":1.0,"reasoning_tokens":1890,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T23:22:38.148897+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a real data-science operation whose implementation is size-dependent (for example, a library routine that switches to a parallel or blocked algorithm above a certain container size, or one with random tie-breaking), run the paper's small-container perturbation procedure on it, and compare the learned lineage with the lineage obtained by instrumenting the implementation on a large input. If the predictions diverge on any operation, the proposed small-to-large generalization is falsified.","supporting_citations":[{"cited_title":"Palkar, J","cited_arxiv_id":null,"evidence_quote":"Motivates the whole IR architecture by showing how a common intermediate representation enables cross-library optimizations."},{"cited_title":"Cheung, A","cited_arxiv_id":null,"evidence_quote":"Provides the 'verified lifting' analogy: translating low-level operations into a platform-agnostic higher-level representation."},{"cited_title":"Cheney, L","cited_arxiv_id":null,"evidence_quote":"Defines why-provenance and witness-set variations on which the direct and indirect influence lineage definitions are built."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Shows algebraic semiring structures for relational provenance, which lineage-constraint tags generalize beyond."},{"cited_title":"Zhao and S","cited_arxiv_id":null,"evidence_quote":"Supplies the compression and in-situ query techniques used to store the relational influence-lineage tables."}],"review_version":1}