🤖 AI

CHRONOS: Temporally-Aware Multi-Agent Coordination for Evolving Data Marketplaces

CHRONOS is a three-layer architecture for temporal knowledge-graph data marketplaces that unifies neural-ODE-based recall optimization, changepoint-aware Shapley pricing, and EXP3-IX differential privacy to address the coupled failures of stale indexing, value misattribution, and budget over-consumption in evolving data environments.

Original authors: Joydeep Chandra

Published 2026-05-25

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Joydeep Chandra

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a bustling, high-tech digital farmers' market where farmers (data sellers) bring fresh produce (knowledge graph data) to sell to chefs (buyers). The catch? The market is constantly changing. New crops appear daily, old ones rot, and the weather (market trends) shifts unpredictably.

The paper introduces CHRONOS, a new system designed to run this market fairly, quickly, and securely, even as the data evolves. It solves three major problems that usually break such markets:

1. The "Stale Map" Problem (Indexing)

The Issue: Imagine the market has a giant, pre-drawn map (an index) showing the fastest shortcuts between stalls. If a farmer moves their stall or a new path opens up, the old map becomes wrong. In digital terms, "shortcut edges" in the data become stale, causing the system to miss good results (low recall).
The CHRONOS Solution (T-LEGEND): Instead of redrawing the whole map every time (which is slow and expensive), CHRONOS uses a "smart decay" engine (Neural ODE). Think of it like a map that automatically fades out old, unused paths and highlights fresh ones based on how recently they were used.

The Result: The system knows exactly how much accuracy it might lose as the map gets slightly outdated, providing a mathematical "safety guarantee" that the results won't drop below a certain level.

2. The "Unfair Price" Problem (Valuation)

The Issue: How do you pay farmers fairly? Usually, systems use a static formula (like Shapley values) to calculate how much each farmer contributed to a dish. But if a sudden trend happens (e.g., everyone suddenly wants kale because of a health scare), the value of kale spikes. A static formula keeps paying the old price, which is unfair.
The CHRONOS Solution (Event-Conditioned MPV): CHRONOS acts like a trend-spotting manager. It watches for "changepoints" (sudden shifts in what buyers want). When a shift is detected, it instantly recalculates the value of the data based on the new reality, not the old one.

The Result: Farmers get paid based on the current value of their data, ensuring fair incentives even when the market goes wild.

3. The "Shared Battery" Problem (Coordination)

The Issue: The market has a limited "privacy battery" (a Differential Privacy budget). Every time the system updates the map or recalculates prices, it uses up some battery. If too many agents try to do this at once, the battery dies, and the market stops protecting people's privacy.
The CHRONOS Solution (Temporal Coordinator): This is the traffic controller. It uses a smart scheduling algorithm (EXP3-IX) to decide when to update the map and when to recalculate prices. It spreads the work out so the battery lasts longer, ensuring the market stays open and private for as long as possible.

The Result: The system gets the most work done without running out of privacy protection.

The "Trusted Curator" & The "Noise" Trade-off

CHRONOS operates under a Trusted Curator model. Imagine a neutral market manager who holds all the raw data.

Public vs. Private: The manager uses public, pre-existing data to build the main map (free of privacy costs). The private, sensitive data from farmers is only used to add a layer of "noise" (random static) to a summary sheet before it's released.
The Trade-off: The paper admits that the "summary sheet" (the privacy-protected data) is very noisy. It's like trying to hear a whisper through a loud fan. You can't read the exact numbers on the sheet.
The Workaround: However, the system doesn't need to read the noisy numbers perfectly to work. It uses the public map to find the right area, and the noisy summary just helps the manager decide when to update things. For paying farmers, the system uses a special "multi-epoch" method: it averages out the noise over time (like averaging several noisy weather reports) to get a reliable trend, allowing for fair payouts without revealing individual secrets.

The Bottom Line

CHRONOS is a three-layer system that:

Keeps the map fresh without rebuilding it from scratch.
Pays farmers fairly based on real-time market shifts.
Manages the privacy budget like a careful accountant to ensure it doesn't run out.

The paper claims this system achieves a sweet spot: it is fast (about 2.7 queries per second), accurate (93.7% recall), and maintains strong privacy (a specific privacy score of 4.25), all while handling up to 500 sellers. It proves you can have a dynamic, evolving data market that is both useful and private, provided you accept that the raw private numbers are hidden behind a veil of noise, while the system's logic does the heavy lifting.

Technical Summary: CHRONOS

1. Problem Statement

Temporal Knowledge Graph (KG) data marketplaces face three coupled failures when designed with static architectures:

Stale Indexing: Hybrid vector-graph indices (e.g., HNSW) rely on shortcut edges built at construction. As the underlying KG evolves (edges added/removed), these shortcuts become stale, silently degrading recall. Existing dynamic systems handle vector updates but fail to model graph-structural staleness or provide recall bounds tied to evolution rates.
Stationary Valuation: Fair data attribution typically relies on Shapley values, which assume a stationary characteristic function. In evolving marketplaces, distributional shifts (e.g., disease outbreaks, regulatory changes) cause marginal dataset values to shift sharply. Static valuations misattribute value, distorting marketplace incentives.
Uncoordinated Privacy Budget: Production marketplaces run concurrent agents sharing a finite differential privacy (DP) budget. Without coordination, simultaneous demands for index updates, valuation recomputation, and query processing exhaust the budget prematurely. Existing frameworks lack formal coupling between scheduling and DP consumption.

These challenges are non-decomposable because index updates, valuation recomputation, and waiting all consume from the same finite $(\epsilon, \delta)$ allowance.

2. Methodology: The CHRONOS Architecture

CHRONOS is a trusted-curator, three-layer architecture that provides a unified treatment of these challenges with explicit public/private separation.

Layer 1: T-LEGEND (Temporal Hybrid Index)

T-LEGEND applies neural-ODE temporal decay to shortcut edges, allowing the index to degrade gracefully rather than failing silently.

Mechanism: A neural ODE models the decay of edge utility over time ( $\Delta t$ ). The decay function is the first component of the ODE solution, trained on historical KG snapshots using contrastive temporal loss.
Public/Private Separation: The index structure ( $H_T$ ) and neighborhood lists are built deterministically from public pre-marketplace data (frozen embeddings and community partitions). Seller-contributed edges do not alter the index topology; they only influence the epoch-level private affinity matrix.
Theoretical Guarantee: The system provides a per-query expected recall-loss bound of $O(P_q \lambda \Delta t)$ . A novel monotone-envelope certificate tightens this bound, reducing the gap between the theoretical bound and observed loss to 1.8–3.2 $\times$ . Formal bounds are also extended to Hawkes dynamics to handle correlated edge changes.

Layer 2: Event-Conditioned MPV (EC-MPV)

This layer conditions Shapley valuation on distributional changepoints detected by BOCPD (Bayesian Online Changepoint Detection).

Mechanism: Instead of continuous recomputation, valuations are batched and conditioned on detected events ( $E$ ). The marginal contribution of a seller is calculated as $\phi_i(D_{priv} \cup D_{pub} | E, t) - \phi(D_{pub} | E, t)$ .
Efficiency: It employs Variance-Reduced Data Shapley (VRDS) with control variates to lower sampling variance.
Guarantees: The system provides finite-sample error guarantees under coalition sampling and DP noise, with a temporal efficiency identity ensuring the sum of valuations equals the total value of the private data contribution.

Layer 3: Temporal Coordinator

A meta-agent that schedules operations (Index Update, Revaluation, or Null) to enforce the shared DP budget.

Algorithm: Uses EXP3-IX (a multi-armed bandit algorithm) over three scheduling actions.
Regret: Achieves $O(\sqrt{T \log T})$ regret while enforcing $(\epsilon_{total}, \delta_{total})$ -DP via moments accounting.
Budget Management: It balances competing demands, ensuring that index maintenance and valuation do not starve each other. It overrides actions that would violate the budget, converting them to "Null" or "Index Update" as safety overrides.

Privacy Mechanism: Fixed-Dimension DP Pipeline

CHRONOS employs a strict public/private separation:

Public: Embeddings, index structure, and query vectors incur zero DP cost.
Private: Seller edges, valuation scores, and index staleness statistics are protected.
Release Policy: The system releases a fixed-dimension privatised affinity matrix ( $\tilde{A}(t)$ ) once per active epoch using the Gaussian mechanism.
Post-Processing: All per-query retrieval and top- $k$ ranking are performed as post-processing on the noisy matrix. Consequently, they incur no extra privacy cost.
Accounting: The system uses standard additive zCDP composition over $\rho$ , achieving a total $\epsilon = 4.25$ at $\delta = 10^{-6}$ across multiple mechanisms (index stats, valuation, affinity).

Settlement Mechanism

To address the noise-dominated nature of external valuation releases (where noise std $\gg$ signal), CHRONOS introduces a multi-epoch coalition-level settlement mechanism. By aggregating valuations over $W$ epochs and grouping sellers into coalitions, the Signal-to-Noise Ratio (SNR) improves, enabling trend-level attribution (e.g., distinguishing above/below median contribution) at $W \ge 7$ epochs.

3. Key Results

Experiments were conducted on four benchmarks: FB15K-237, WN18RR (synthetic), MIMIC-IV, and Yelp (real-world).

Performance: CHRONOS achieves 0.937 recall@10 on Yelp with 2.74 queries/s and a P50 latency of 161 ms.
Recall Stability: On MIMIC-IV, T-LEGEND degrades at only 0.0021 recall points/day, a 4.2 $\times$ improvement over Plain-HNSW and 2.8 $\times$ over FreshDiskANN.
Privacy-Utility Trade-off: At matched $\epsilon=4.25$ , CHRONOS significantly outperforms per-query DP mechanisms (e.g., OneShot Laplace, Joint Exponential), which suffer 6–10 $\times$ lower QPS (0.28–0.43 vs. 2.74).
Scalability: The system scales to 500 sellers. As the number of sellers ( $n$ ) increases, sensitivity decreases ( $\propto 1/\sqrt{n}$ ), causing the total $\epsilon$ to grow sublinearly (from 4.25 at $n=10$ to 5.13 at $n=500$ ).
Coordination Impact: Removing the Temporal Coordinator (using round-robin) degrades recall by 3.3 points and increases $\epsilon$ by 26.6%, confirming the necessity of joint design.
VSAG Comparison: While VSAG (a production HNSW) offers higher raw QPS, it lacks temporal KG scoring. Integrating VSAG's layout with CHRONOS's decay-aware construction is projected to yield a 1.5 $\times$ speedup without sacrificing recall.

4. Significance and Claims

The paper claims that CHRONOS represents the first system to couple index freshness, valuation correctness, and coordinated DP budget management within a multi-agent framework for temporal knowledge graphs.

Unified Treatment: It demonstrates that these three challenges cannot be solved in isolation; a joint design is required to prevent budget exhaustion and performance degradation.
Theoretical Rigor: The work provides formal recall bounds (Theorems 2–4) that incorporate ODE Lipschitz structures and Hawkes processes, moving beyond static assumptions.
Practical Privacy: It establishes a viable operating point for high-utility, low-latency retrieval under strict DP constraints by leveraging public index structures and amortizing DP costs over epochs rather than per query.
Actionable Settlement: It offers a concrete mechanism for seller payouts that reconciles the high noise of DP releases with the need for fair attribution, using coalition aggregation to recover signal.

5. Limitations

The authors explicitly acknowledge several limitations:

Bound Looseness: The monotone-envelope bound remains 1.8–3.2 $\times$ looser than observed loss; closing this gap requires path-correlation analysis at hub nodes.
Noise-Dominated Signals: At the chosen privacy level ( $\epsilon=4.25$ ), externally released valuations and affinity scores are dominated by noise. The system's utility derives primarily from public index routing and adaptive scheduling driven by low-sensitivity DP statistics, not from the private signal itself.
Trust Model: The current design relies on a trusted curator holding all raw seller data. While two-server and Local DP extensions are proposed as future work, they are not fully implemented or validated in this study.
Query Privacy: Buyer queries are treated as public. If queries are sensitive, additional mechanisms (e.g., count-min sketches) are required, which are not part of the core evaluation.