Serve graph features and representations with a coherent freshness policy
Trace dependencies, stale publications and model-compatible cache versions.
On this page
The question for today
What you’ll understand
- Identify the dependency set of a cached graph representation.
- State a finite staleness bound with delayed-publication assumptions.
- Choose an explicit fresh, stale or unavailable serving behavior.
A cached node vector can become obsolete when its own feature changes, when a neighbor changes, when topology changes or when the encoder is released. A cache hit therefore says little about whether the answer matches the requested graph and model state. A serving design needs an explicit freshness and compatibility contract that follows all dependencies used to compute the representation, including late computations that can publish stale results after an update.
Freshness follows the representation’s dependencies
A one-hop representation can depend on the node feature, the neighbor set, neighbor features, normalization degrees and model parameters. A multilayer representation can depend on a wider receptive field. Invalidating only the directly updated node leaves dependent cached vectors unchanged. An update system can track dependencies, recompute affected regions, use versioned snapshots or explicitly accept bounded staleness. These strategies have different costs, but each must define what model and data state a served vector actually represents.
Freshness is also different from historical causality. Recomputing a historical query using the newest graph can introduce future information rather than improve its correctness. A request should identify whether it wants current state, an immutable snapshot or a permitted historical cutoff. Include model release, feature schema and graph epoch in cache compatibility. A vector generated by an old encoder may have the right dimension while belonging to an incompatible representation space, especially when a downstream classifier or ranking index was updated independently.
A TTL bound needs a bound on stale publication
Suppose a source change occurs at time zero and the system proves that no stale result can be accepted into a cache after duration L. That proof must include every old read, queued computation, response and cache-fill delay, or fence stale versions at publication. If a cache entry then lives at most C seconds and every new request rejects expired entries, stale acceptance ends no later than L+C. Allowing stale-on-error or unchecked replicas changes this guarantee and must be accounted for separately.
A TTL alone gives no finite global visibility bound when an old computation can pause indefinitely and later publish a stale result with a fresh TTL. Limit publication by version fencing or trusted observation age, not just by expiring already stored entries. Model rollout has the same issue: an old encoder’s in-flight result can refill a nominally cleared cache unless its release is validated at insertion or lookup. A successful invalidation command does not prove those delayed writers have stopped.
Make freshness observable and failure behavior deliberate
Report source observation age, graph and model versions, update backlog, stale-publication rejection and the fraction of requests served under an explicit degraded policy. Choose whether insufficiently fresh data causes recomputation, a bounded stale response or an unavailable result. Do not silently change that behavior during failures. Compare offline and online feature definitions using the same timestamp and neighborhood rules. A feature can be freshly computed yet semantically wrong if serving uses a different edge direction, degree normalization or exclusion policy from training.
The cache lab deliberately lacks freshness state. Reset and set both C=4 and s=4; predict four misses and twelve hits in its initial sixteen requests. Step predicts one more hit, yielding thirteen hits and four misses. Requests follow (i·s) mod 16 with N=min(4096,16+floor(2t)). The stored objects are abstract addresses without values, timestamps or TTLs. Use the unchanged hit count to explain what a cache metric cannot establish: this instrument cannot certify feature age, model compatibility or successful invalidation.
Work it through
Bound new-request stale acceptance after fencing old fills
At a source change, a serving design budgets two seconds for update detection, three more for dependent recomputation and five more for publication and draining or fencing every old fill. Assume these are proven sequential upper bounds through the last accepted stale publication. Every cache then retains an entry at most four seconds, rejects it on expiry and never serves stale-on-error.
The proven publication horizon is L=2+3+5=10 seconds from the source change. The final five-second premise explicitly includes delayed old computations and fills; it is stronger than saying a new fresh vector usually finishes in ten seconds.
A stale result accepted just before that ten-second boundary can receive at most another four seconds of residency. Thus the last possible stale acceptance on a new request is bounded by L+C=10+4=14 seconds from the source change.
A request around second 13 could still encounter such an unexpired late stale entry. At or beyond the stated bound, the assumptions require expired or fenced stale entries to be rejected. If fresh recomputation is unavailable, the design must fail according to its declared policy rather than extend stale acceptance.
Fourteen seconds bounds new-request stale acceptance under the stated premises, not response completion. Previously accepted requests can finish later. The drain or fencing proof and every request path’s expiry check are necessary.
The living notebook
Explore the model
Interactive lab · cache
A cache hit has no built-in freshness meaning
Reset → set C=4 and s=4 → predict misses 4 and hits 12. Step adds a hit: misses 4, hits 13. The exact toy request count caps at 4096.
- Hits / requests
- 0 / 16
- Hit rate
- 0%
- Address-stream period
- 16 addresses
A fully associative LRU cache starts empty and requests address (i·s) mod 16. Hits move an address to the newest position; misses evict the oldest when full. Playback starts with 16 requests and adds two per second, capped at 4096 explicitly simulated requests. This toy stream is not a processor-cache benchmark. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.
Look forThe LRU model stores addresses only. No timestamp, value, model release or TTL is represented, so its hit count cannot establish freshness.
Pause & reason
Check your understanding
Your turn
Try it yourself
A design proves no stale fill is accepted after six seconds and entries expire after at most three additional seconds on every new-request path. What bound follows? What changes if an unbounded old computation may later insert a stale value with a fresh three-second TTL?
Take a moment to make a prediction or work it out on paper. Open a hint when you need one.
Give me a hint
Use the last accepted publication horizon, not merely the time a replacement is first available. Check whether the second scenario retains that premise.
Compare with the solution
The first design bounds stale acceptance by 6+3=9 seconds from the change. In the second scenario the six-second publication bound no longer holds, so the three-second TTL alone gives no finite global guarantee. A version fence, a bounded fill delay or expiry anchored to a trusted earlier observation is needed to restore an appropriate bound.
Keep the idea
Take it with you
- Cached graph vectors depend on topology, features and model compatibility.
- Finite staleness bounds must cover delayed stale publication.
- Current freshness and historical information eligibility are different requirements.
Read further
Original sources and deeper explanations to follow at your own pace.
Optional progress, saved in this browser when available. Revisit any lesson at any time.
Lesson not marked complete.