CHRONOS marries neural-ODE decay, changepoint-aware Shapley pricing and DP-bandit scheduling to boost retrieval recall to 0.937@10 while enforcing epsilon=4.25 (delta=1e-6), but at this privacy level released valuations are noise-dominated so most utility comes from public index routing and low-sensitivity scheduling.
CHRONOS: Temporally-Aware Multi-Agent Coordination for Evolving Data Marketplaces
CHRONOS is a three-layer architecture for temporal knowledge-graph data marketplaces that combines neural-ODE temporal decay, changepoint-conditioned Shapley valuation, and privacy-aware bandit scheduling to improve retrieval recall and enforce differential privacy while providing theoretical performance guarantees.
Temporal knowledge-graph data marketplaces face three coupled failures in static designs: stale hybrid index shortcuts reduce recall as edges evolve, stationary Shapley pricing misattributes value after distribution shifts, and uncoordinated agents over-consume a shared differential-privacy budget. We present CHRONOS, a three-layer architecture providing a unified treatment of these challenges with explicit public and private separation. Layer one applies neural-ODE temporal decay to shortcut edges, providing a per-query expected recall-loss bound of Big-O of Pq lambda delta t, with a monotone-envelope guarantee reducing bound looseness to 1.8 to 3.2 times observed loss. Layer two conditions Shapley valuation on detected changepoints and provides finite-sample error guarantees under noise. Layer three uses EXP3-IX to achieve Big-O of the square root of T log T regret while enforcing epsilon and delta differential privacy via moments accounting. CHRONOS releases a privatized affinity matrix per epoch using the Gaussian mechanism; all retrieval and ranking are post-processing, incurring no extra privacy cost. We provide multi-epoch settlement, scalability analysis for 500 sellers, and comparisons against accelerated baselines. Across four benchmarks, CHRONOS shows 0.937 recall at ten, 2.74 queries per second, 161 ms latency, and total epsilon of 4.25 at delta of 10 to the power of negative 6 under zCDP composition. These results indicate a competitive operating point. A limitation is that at this privacy level, released valuations remain noise-dominated; utility derives primarily from public index routing and adaptive scheduling driven by low-sensitivity statistics.
Summary
Main Finding
CHRONOS is an end-to-end architecture for temporal knowledge-graph (KG) data marketplaces that jointly addresses (1) index staleness, (2) temporally-varying Shapley valuation, and (3) multi-agent coordination under a shared differential-privacy (DP) budget. By (i) applying a neural-ODE temporal decay to public shortcut edges (T-LEGEND), (ii) conditioning Shapley-style marginal-value (MPV) calculations on BOCPD-detected changepoints (Event-Conditioned MPV), and (iii) scheduling index/valuation actions with an EXP3-IX coordinator that enforces adaptive DP composition, CHRONOS attains provable temporal recall/valuation bounds, sublinear coordination regret, and an end-to-end DP accounting. Empirically it achieves a competitive recall/latency/privacy operating point (recall@10 = 0.937, P50 latency = 161 ms) at total ε = 4.25 (δ = 1e-6 under zCDP composition).
Key Points
- Architecture (three layers)
- Layer 1 — T-LEGEND: neural-ODE temporal decay applied to public HNSW shortcut edges; index structure itself is public and frozen per epoch, while private seller edges never enter the fixed neighbor lists. This yields graceful index degradation instead of silent recall loss.
- Layer 2 — Event-Conditioned MPV: Shapley marginal-value (MPV) estimates are conditioned on changepoints detected by BOCPD and use variance-reduction (VRDS) + permutation sampling; marginal contributions are clipped to bound sensitivity.
- Layer 3 — Temporal Coordinator: EXP3-IX meta-agent over three actions {INDEX-UPDATE, REVALUE, NULL} with bandit feedback; achieves O(√(T log T)) regret and enforces (ε_total, δ_total)-DP via Rényi / zCDP moments accounting.
- Formal guarantees and analyses
- T-LEGEND per-query expected recall-loss bound O(P_q λ Δt) (Theorem 1) with a monotone-envelope ODE certificate that tightens worst-case looseness (empirically reduces looseness to 1.8–3.2× observed loss). Extensions to correlated arrivals via Hawkes-process bounds (Theorem 4).
- EC-MPV: finite-sample estimation error bounds that account for coalition sampling, DP noise, and changepoint uncertainty (Theorem 7).
- Coordinator: regret bound O(√(T log T)) (Theorem 10) and formal sensitivity proofs for DP composition (Proposition 8).
- DP design and public/private separation
- Trusted-curator model: public (zero-cost) components include pre-marketplace embeddings, frozen HNSW neighborhood lists, and public timestamps for pre-marketplace edges; private components include post-launch seller edges and valuations.
- Fixed-dimension epoch-level Gaussian mechanism releases a privatized affinity matrix eA(t) once per active epoch; per-query retrieval/top-k ranking are DP-free post-processing.
- Per-entry noise calibration and compositional accounting: per-entry noise magnitudes are large (authors report σ_entry ≫ signal), yielding per-entry ε_entry ≈ 0.0011 and total ε = 4.25 at δ = 1e-6 via additive zCDP composition over ρ.
- Practical results & system behavior
- Experiments on four benchmarks (including FB15K-237 / WN18RR synthetic, MIMIC-IV, Yelp) report recall@10 = 0.937, throughput ≈ 2.74 queries/s, P50 latency 161 ms, and total ε = 4.25 (δ = 1e-6). Scalability evaluated up to 500 sellers.
- Seller settlement: multi-epoch coalition-level payout mechanism with SNR analysis—trend-level attribution becomes feasible at window W ≥ 7 epochs and coalition size n_coal ≤ 5.
- Limitations noted by authors
- Trusted-curator assumption (single operator holds raw seller data); two-server or local-DP extensions are possible but come with costs.
- Query privacy not protected by default (buyer queries treated as public).
- At the chosen privacy operating point, externally released valuations and affinity scores are largely noise-dominated; most utility comes from public index routing and low-sensitivity DP statistics.
Data & Methods
- Datasets / dynamics
- Benchmarks: four datasets including standard KG splits (FB15K-237, WN18RR) and real-world temporal KGs (MIMIC-IV, Yelp). Baseline Poisson edge-change model with estimated rates (e.g., λ ≈ 12 on MIMIC-IV, λ ≈ 2.9 on Yelp); Hawkes extensions analyzed theoretically.
- Layer 1: T-LEGEND
- Neural-ODE decay: decay(Δt) := σ(h(Δt)[1]) where dh/dΔt = f_θ(h, Δt), h(0) = const; f_θ is a small MLP (two-hidden-layer Softplus), trained with a contrastive temporal loss (LODE) on historical snapshots (months 1–6 training, months 7–8 val, 9–12 test).
- Index: public HNSW-like neighborhood lists built deterministically on public embeddings; temporal decay applies to weights, not to the fixed neighbor lists.
- Theoretical recall-loss bound O(P_q λ Δt) (Theorem 1) and ODE-certified monotone-envelope tightening (Theorem 3).
- Layer 2: Event-Conditioned MPV
- Changepoint detection: BOCPD (Normal-Inverse-Wishart conjugate prior, geometric hazard π_cp = 1/250). Changepoints declared at posterior probability > 0.85.
- Valuation: MPV_i(t, E) = φ_i(D_priv ∪ D_pub | E,t) − φ(D_pub | E,t), v(S; E) uses MRR conditioned on event E. Use permutation sampling (m = 1,000) + VRDS control variates to reduce variance; clip marginals to [−B,B] with B = 0.2 to bound sensitivity.
- Finite-sample and DP-noise-aware error bounds given (Theorem 7).
- Layer 3: Temporal Coordinator
- Bandit scheduling: EXP3-IX over d = 3 actions, epochs = 60 s; importance-weighted loss updates with exploration parameter γ; budget-violating actions overridden to NULL.
- Reward balances QPS, recall proxy and privacy consumption: R = QPS + μ_R R̂ − ν ε_consumed (μ_R = 10, ν = 5).
- Regret guarantee O(√(T log T)); DP enforced by moments accounting with per-step Rényi moments μ_t(α) = α/(2 σ_t^2) and zCDP composition.
- DP pipeline & public/private mechanics
- Public/private split: public pre-marketplace embeddings & HNSW; private seller edges clipped by a public hash-based ordering to an active scope; Gaussian mechanism applied to the fixed-dimension affinity matrix per epoch.
- Per-entry noise calibrated to dimension-aware sensitivity (Proposition 1); reported per-entry σ_entry very large (authors note σ_entry = 885 in an example), making released affinities and valuation signals noise-dominated at the chosen ε.
- Experimental evaluation
- Throughput/latency benchmarks vs. VSAG-accelerated baselines; head-to-head DP retrieval at matched ε; DP vs cryptographic (MPC/TEE) cost analysis (crypto incurs 10–100× latency).
- Robustness tests: seller-skew stress tests, three drift detectors, five coordinator strategies. Scalability analysis up to 500 sellers.
Implications for AI Economics
- Temporal correctness matters for marketplace incentives
- Static Shapley valuations misattribute value after distributional shifts; conditioning valuations on detected events aligns payments with event-driven marginal value and thereby preserves correct incentives for seller behavior during outbreaks, regulatory changes, or other sudden shifts.
- Privacy budget is a scarce shared resource that couples system decisions
- CHRONOS illustrates that index maintenance (freshness), valuation recomputation (fair pricing), and coordination (scheduling) all consume the same DP budget and must be jointly scheduled. Marketplace designers must allocate privacy budget explicitly across these operational needs; misallocation (e.g., spending budget on frequent rebuilds) can starve valuation recalculation and distort payments.
- Signal/noise trade-offs and economic transparency
- At realistic privacy settings used in the paper (ε ≈ 4.25), externally released valuations and affinity scores can be noise-dominated. This weakens price signals and raises risks for seller trust and market efficiency: buyers and sellers may not be able to rely on noisy published valuations, shifting more reliance onto observable public routing and coordinator-driven decisions. Designers should expect a tension between strong privacy and transparent, actionable pricing.
- Time-lagged settlements and seller liquidity
- The multi-epoch coalition-level settlement requires W ≥ 7 epochs to achieve trend-level attribution; this implies delayed and aggregated payouts. For sellers who require prompt revenue (e.g., small data providers), delayed / aggregate settlements could discourage participation unless mitigated by advances in low-sensitivity stats, subsidized early payments, or alternative trust models.
- Trust model matters for market structure and participation
- CHRONOS adopts a trusted-curator model; moving to two-server or local-DP variants relaxes trust but increases cost or lowers utility (local-DP needs more data; two-server requires protocol work). Marketplaces must weigh operator trust vs. participation costs and possible regulatory constraints.
- Operational scalability and feasibility
- The system scales to hundreds of sellers and achieves reasonable latency (P50 161 ms) and throughput for production-style queries, suggesting temporally-aware DP marketplaces are practically feasible for medium-size markets (e.g., clinical or pharma knowledge graphs), not only theoretical constructs.
- Policy and mechanism design insights
- Using event-conditioned valuations and adaptive scheduling provides a formal mechanism to prioritize scarce privacy resources around high-value events (e.g., outbreaks), which could be aligned with social welfare objectives when platform designers set reward weights (μ_R, ν). Regulators and platform designers can leverage such mechanisms to balance privacy, freshness, and fairness in data markets.
- Open economic questions
- How to set privacy budget pricing and seller compensation in light of noisy valuation releases remains unsettled. If published valuations are noisy, off-chain bilateral contracts or reputational mechanisms might complement DP-released statistics. Also, the impact of delayed settlement on market entry/exit dynamics, and strategic behavior around changepoint detection, are important areas for future economic analysis.
Summary takeaway: CHRONOS offers a concrete, theoretically-grounded design that demonstrates how temporal index freshness, event-aware valuation, and DP-aware coordination can be jointly managed in a knowledge-graph marketplace. For AI-economics, its core lesson is that privacy is not an orthogonal constraint—privacy accounting fundamentally reshapes indexing and pricing trade-offs, so marketplace mechanisms, settlements, and incentive designs must be co-optimized with privacy-aware operational scheduling.
Assessment
Paper Typeother
Evidence Strengthlow — The paper provides theoretical guarantees and system-level benchmarks on four (unspecified) datasets and simulated sellers, but it does not identify causal effects on economic outcomes (prices, welfare, adoption) in real markets; experimental results are lab/benchmark-focused and valuations are reported as noise-dominated under realistic privacy settings, limiting inference about marketplace behavior.
Methods Rigormedium — The work combines provable components (neural-ODE decay bounds, finite-sample Shapley error guarantees, regret bounds for EXP3-IX, zCDP accounting) and empirical benchmarks, indicating solid technical rigor; however, evaluation lacks real-world deployment, explicit economic outcome measurement, and transparency about benchmark datasets and seller behavior models.
SampleEvaluation on four temporal knowledge-graph retrieval benchmarks (datasets not named in the summary), multi-epoch simulated marketplace experiments with a scalability analysis up to 500 sellers, comparisons to accelerated baselines, and measurement of recall@10, throughput (queries/sec), latency, and composed privacy cost (epsilon=4.25, delta=1e-6) under zCDP; affinity matrices per epoch are privatized with Gaussian noise and retrieval/ranking treated as post-processing.
Themesgovernance adoption
GeneralizabilityBenchmarks/datasets not described — may not match real-world temporal knowledge graphs or marketplace heterogeneity, Seller behavior appears simulated rather than observed from deployed markets, Valuations are noise-dominated at reported privacy levels, so results rely heavily on public index routing and may not transfer where private signals are crucial, Scalability validated up to 500 sellers; larger markets and richer strategic behavior untested, Specific modeling choices (neural-ODE decay, changepoint detector, EXP3-IX) may not generalize across domains or non-stationary environments
Claims (13)
| Claim | Direction | Confidence | Outcome | Details |
|---|---|---|---|---|
| Static temporal knowledge-graph data marketplace designs suffer three coupled failures: (i) stale hybrid index shortcuts reduce recall as edges evolve, (ii) stationary Shapley pricing misattributes value after distribution shifts, and (iii) uncoordinated agents over-consume a shared differential-privacy budget. Market Structure | negative | high | marketplace failures (recall reduction, pricing misattribution, privacy budget overconsumption) |
0.12
|
| Layer one of CHRONOS applies neural-ODE temporal decay to shortcut edges and provides a per-query expected recall-loss bound of Big-O(Pq lambda delta t). Output Quality | positive | high | recall (expected recall-loss per query) |
Big-O of Pq lambda delta t
0.12
|
| The monotone-envelope guarantee in layer one reduces bound looseness to 1.8 to 3.2 times observed loss. Output Quality | positive | high | tightness of recall-loss bound (bound looseness ratio) |
1.8 to 3.2 times observed loss
0.12
|
| Layer two conditions Shapley valuation on detected changepoints and provides finite-sample error guarantees under noise. Market Structure | positive | high | accuracy/error of Shapley-based valuations |
finite-sample error guarantees under noise
0.12
|
| Layer three uses EXP3-IX to achieve Big-O(sqrt(T log T)) regret while enforcing (epsilon, delta)-differential privacy via moments accounting. Decision Quality | positive | high | regret of the online allocation algorithm |
Big-O of sqrt(T log T) regret
0.12
|
| CHRONOS releases a privatized affinity matrix per epoch using the Gaussian mechanism; all retrieval and ranking are post-processing and thus incur no extra privacy cost. Ai Safety And Ethics | positive | high | privacy accounting / composition (privacy cost per epoch and downstream operations) |
privatized affinity matrix released per epoch via Gaussian mechanism; post-processing incurs no extra privacy cost
0.12
|
| The paper includes a scalability analysis for 500 sellers (multi-epoch settlement). Market Structure | positive | high | scalability with respect to number of sellers |
n=500
scalability analysis for 500 sellers
0.06
|
| The paper reports empirical results across four benchmarks showing CHRONOS achieves 0.937 recall at ten (recall@10). Output Quality | positive | high | recall@10 |
n=4
0.937 recall at ten
0.12
|
| Across the benchmarks CHRONOS attains 2.74 queries per second throughput. Organizational Efficiency | positive | high | throughput (queries per second) |
n=4
2.74 queries per second
0.12
|
| Measured latency for CHRONOS is 161 ms. Task Completion Time | positive | high | latency |
n=4
161 ms latency
0.12
|
| CHRONOS achieves a total privacy loss of epsilon = 4.25 at delta = 10^-6 under zCDP composition in the reported experiments. Ai Safety And Ethics | positive | high | privacy budget (epsilon, delta) |
n=4
total epsilon of 4.25 at delta of 10^-6 under zCDP composition
0.12
|
| A reported limitation is that at this privacy level the released valuations remain noise-dominated; the system's utility derives primarily from public index routing and adaptive scheduling driven by low-sensitivity statistics. Output Quality | negative | high | utility source (valuation signal vs. public index routing/adaptive scheduling) |
released valuations remain noise-dominated at reported privacy level
0.12
|
| The paper includes comparisons against accelerated baselines (reported experimental comparisons). Other | null_result | high | comparative performance vs. baselines |
0.06
|