Data marketplaces built on temporal knowledge graphs face a coordination problem that static designs cannot solve. Three systems must evolve together: hybrid graph indexes that decay as edges change, Shapley pricing that drifts after distribution shifts, and differential-privacy budgets consumed by uncoordinated agents. When one system updates without the others, recall drops, sellers get mispriced, and privacy budgets exhaust.
CHRONOS addresses this with a three-layer architecture that treats temporal evolution as a first-class concern. The paper (arXiv 2605.23887v1) documents how neural-ODE decay models, changepoint-conditioned Shapley valuation, and EXP3-IX bandit algorithms coordinate around a shared privacy budget.
The Three-Way Coordination Problem
Hybrid index decay. Knowledge-graph marketplaces use shortcut edges to accelerate retrieval. As the underlying graph evolves, shortcuts become stale. A query that should return ten results might return seven because three relevant edges have changed. Static re-indexing schedules either waste compute or miss drift.
Shapley pricing drift. Shapley values attribute revenue to data sellers based on marginal contribution. When the query distribution shifts, yesterday’s high-value seller becomes low-value today. Stationary pricing misattributes value, causing agents to over-bid for stale data or under-bid for newly relevant sources.
Privacy budget exhaustion. Multiple agents query the same marketplace. Each query consumes epsilon from a shared differential-privacy budget. Without coordination, agents race to the bottom, exhausting epsilon before the epoch ends. Late-arriving agents get no service.
CHRONOS Architecture
CHRONOS separates public and private operations across three layers.
Layer One: Temporal Index Decay
The system models shortcut edge relevance using neural ODEs. Each shortcut has a decay function parameterized by lambda (decay rate) and delta-t (time since last update).
Expected recall loss per query is O(Pq * lambda * delta-t), where Pq is query-specific path probability. The monotone-envelope guarantee bounds looseness to 1.8x to 3.2x observed loss, meaning the theoretical bound stays close to actual degradation.
When expected recall loss crosses a threshold, the system triggers incremental re-indexing. Only affected shortcuts are rebuilt, not the entire index.
Layer Two: Changepoint-Conditioned Shapley Valuation
Shapley values are computed within detected changepoint windows. When query distribution shifts, the system detects a changepoint and recomputes valuations for the new regime.
Finite-sample error guarantees hold under noise. The system provides confidence intervals around each seller’s valuation, allowing agents to reason about pricing uncertainty.
Multi-epoch settlement batches payments. Instead of settling after every query, the system accumulates valuations across an epoch and settles once. This reduces transaction overhead and smooths out short-term volatility.
Layer Three: Privacy-Aware Agent Coordination
EXP3-IX (exponential-weight algorithm for exploration and exploitation with privacy) allocates queries across agents while enforcing differential privacy.
Regret is O(sqrt(T log T)), where T is the number of queries. This is competitive with non-private bandits.
Privacy is enforced via moments accounting with the Gaussian mechanism. The system releases a privatized affinity matrix per epoch. All retrieval and ranking are post-processing, so they incur no additional privacy cost.
Total epsilon across epochs is 4.25 at delta = 10^-6 under zero-concentrated differential privacy (zCDP) composition.
Implementation Shape
class ChronosMarketplace:
def __init__(self, lambda_decay, epsilon_budget, delta):
self.index = TemporalHybridIndex(lambda_decay)
self.shapley = ChangePointShapley()
self.privacy = EXP3IX(epsilon_budget, delta)
self.epoch_valuations = []
def query(self, agent_id, query_vector):
# Check privacy budget
if not self.privacy.can_query(agent_id):
return {"error": "privacy_budget_exhausted"}
# Retrieve with decay-aware index
recall_loss = self.index.expected_loss(query_vector)
if recall_loss > THRESHOLD:
self.index.incremental_rebuild(query_vector)
results = self.index.retrieve(query_vector)
# Attribute value to sellers
valuations = self.shapley.attribute(results, query_vector)
self.epoch_valuations.append(valuations)
# Consume privacy budget
self.privacy.record_query(agent_id)
return results
def settle_epoch(self):
# Release privatized affinity matrix
affinity = self.privacy.privatize_affinity(self.epoch_valuations)
# Settle payments
payments = self.shapley.settle(affinity)
self.epoch_valuations = []
return paymentsThe key is that privacy enforcement happens once per epoch, not per query. Retrieval and ranking are deterministic post-processing of the privatized affinity matrix.
Performance Characteristics
| Metric | Value | Notes |
|---|---|---|
| Recall@10 | 0.937 | After decay-aware re-indexing |
| Queries/sec | 2.74 | 500 sellers, single node |
| Latency (p50) | 161 ms | Includes Shapley attribution |
| Total epsilon | 4.25 | At delta = 10^-6, zCDP composition |
| Regret bound | O(sqrt(T log T)) | Competitive with non-private bandits |
Latency includes Shapley valuation, which is the primary latency driver. The system computes marginal contributions for each seller on every query. Incremental Shapley approximations could reduce this cost.
Failure Modes
Changepoint detection lag. If the system detects a distribution shift late, Shapley values remain stale. Agents over-pay for irrelevant data until the next changepoint triggers recomputation.
Privacy budget front-running. Agents with low-latency connections can consume epsilon faster than others. The EXP3-IX allocation is fair in expectation, but individual agents may experience starvation.
Index rebuild storms. If many queries simultaneously cross the recall-loss threshold, the system triggers multiple incremental rebuilds. Without rate limiting, this can saturate compute.
Shapley approximation error. Exact Shapley computation is exponential in the number of sellers. The paper uses sampling-based approximations, which introduce error. Approximation error grows with seller count, and at 500 sellers the system may require additional sampling rounds to maintain accuracy.
Observability Requirements
You need to track:
- Per-query recall loss and re-indexing triggers (e.g.,
chronos_recall_loss_per_query,chronos_index_rebuild_count) - Changepoint detection events and Shapley recomputation latency (e.g.,
chronos_changepoint_detected,chronos_shapley_compute_ms) - Per-agent epsilon consumption and remaining budget (e.g.,
chronos_epsilon_consumed_total,chronos_epsilon_remaining) - Shapley valuation confidence intervals
- Epoch settlement volume and payment distribution
Without these, you cannot debug coordination failures. If recall drops, you need to know whether the index is stale, the privacy budget is exhausted, or Shapley values have drifted.
Deployment Considerations
Seller onboarding. Adding a new seller requires recomputing Shapley values for all existing sellers. This is O(N^2) in the number of sellers. The system batches onboarding to amortize cost.
Privacy budget allocation. The epsilon budget is shared across all agents. You must decide how to allocate it: equal shares, priority-based, auction-based. CHRONOS uses EXP3-IX for exploration-exploitation, but other allocation strategies are possible.
Index storage. Temporal hybrid indexes store both base edges and shortcut edges with decay metadata. Storage grows linearly with the number of shortcuts. At 500 sellers and 10^6 edges, expect 2-3 GB per index.
Settlement finality. Multi-epoch settlement introduces lag between query and payment. Sellers must trust that valuations will be settled correctly. If the system crashes mid-epoch, valuations are lost unless checkpointed.
Technical Verdict
Use CHRONOS when:
- You operate a data marketplace where query distributions shift over time
- Multiple agents query the same knowledge graph and must share a privacy budget
- Sellers need fair attribution based on marginal contribution
- You can tolerate 161 ms query latency for privacy and pricing guarantees
Avoid CHRONOS when:
- Query distributions are stationary (use static Shapley pricing)
- Privacy is not a concern (skip the EXP3-IX layer)
- You need sub-10ms query latency (Shapley attribution is too slow)
- You have fewer than 50 sellers (coordination overhead exceeds benefit)
The architecture is most valuable when all three problems (index decay, pricing drift, privacy exhaustion) occur together. If you only face one or two, simpler designs suffice.