Cache Coherence

These are the two primary protocols for maintaining coherence after a data modification.

• Write Invalidation: When an agent updates data, it sends an invalidation signal to all other caches holding that data. Their copies are marked stale, forcing a fetch on their next read. This is efficient for data that is read frequently but written rarely.
• Write Update (or Write Broadcast): When an agent updates data, it broadcasts the new value to all other caches. This keeps all caches current but generates more network traffic. It's suitable for data that is written to frequently by one agent and read immediately by others.

In agent-side caching, write invalidation is often preferred to minimize bandwidth, with a Time-To-Live (TTL) fallback for robustness.

These define how caches discover and coordinate state changes.

• Snooping Protocol: All caches monitor ("snoop on") a shared broadcast bus or interconnect for coherence transactions. When an invalidation or update is seen, caches take local action. This is simple but doesn't scale well to large, distributed agent fleets.
• Directory-Based Protocol: A centralized directory tracks which agents have cached copies of which data blocks. On a write, the writer consults the directory to know exactly which caches to invalidate or update. This is scalable for distributed systems but introduces a single point of failure and latency for directory access.

Modern AI agent orchestration layers typically implement a hybrid or distributed directory approach for scalability.

The MESI protocol is a canonical snooping protocol where each cached data block can be in one of four states:

• Modified (M): The block is dirty (modified) only in this local cache and must be written back to main memory before being shared. The agent has exclusive ownership.
• Exclusive (E): The block is clean (matches main memory) and is present only in this local cache. The agent can modify it without notifying others.
• Shared (S): The block is clean and may be present in multiple caches. Agents can read it but cannot write without first invalidating other copies.
• Invalid (I): The block is stale or not present; it cannot be used for a read.

State transitions are triggered by local reads/writes and snooped bus transactions (BusRd, BusRdX, etc.). This provides a formal model for reasoning about agent cache state.

These are related but distinct concepts critical for multi-agent reasoning.

• Cache Coherence: Guarantees that all caches see a single, logical view of the memory system for a single memory location. It answers: "If one agent writes to address X, when will other agents see that write?" It's a contract between caches and memory.
• Memory Consistency: Defines the globally visible order of reads and writes to all memory locations by multiple agents. It answers: "If Agent A writes to X and then to Y, in what order can Agent B observe those writes?" It's a contract between the agents and the memory system.

Coherence is necessary but not sufficient for consistency. A system can be coherent (all see the same final value for X) but not consistent (agents disagree on the order of writes to X and Y), leading to non-deterministic agent behavior.

False sharing is a performance degradation that occurs when two independent data variables reside on the same cache line, and different agents frequently modify each variable.

• Mechanism: Cache coherence operates on entire cache lines (e.g., 64 bytes). If Agent A updates Variable X and Agent B updates Variable Y on the same line, the coherence protocol will uselessly invalidate the entire line in both caches, forcing frequent cache misses and memory traffic.
• Impact on Agents: This can severely slow down parallel agent execution, as agents contend for exclusive access to a cache line even though they are accessing logically separate data.
• Mitigation: Data structure padding or alignment to place frequently written, independent agent state on separate cache lines.

Maintaining coherence is uniquely challenging in caches storing semantic or LLM inference results.

• Problem: A semantic cache returns a cached result for a query that is semantically similar but not textually identical to a previous query. If the underlying source data changes, invalidating the correct set of semantic entries is non-trivial.
• Solutions:
  • Tag-Based Invalidation: Cached entries are tagged with the IDs of the source data fragments used to generate them. When source data changes, all entries with that tag are invalidated.
  • Vector Space Invalidation: Track the embedding (vector) of cached queries. When source data changes, compute which semantic regions of the vector space are affected and invalidate nearby entries.
  • Deterministic Cache Guarantees: For pure, side-effect-free LLM tool calls, a deterministic cache can be used where the same inputs (prompt, parameters, model version) always produce the same output, simplifying coherence to a versioning problem.

Cache consistency is the overarching property that ensures data in a cache accurately reflects the state of the primary data source. It is the goal that cache coherence protocols are designed to achieve. Models include:

• Strong Consistency: Guarantees that any read operation returns the most recent write. This is the strictest model and is often required for financial transactions.
• Eventual Consistency: Guarantees that if no new updates are made, all reads will eventually return the same value. This is common in distributed systems like DNS or social media feeds.
• Causal Consistency: Preserves the order of causally related operations, a middle ground between strong and eventual consistency. In agent-side caching, the choice of model directly impacts the risk of serving stale data to an LLM agent.

Cache invalidation is the active process of marking cached data as stale or removing it entirely to enforce consistency. It is a primary method for maintaining cache coherence. Strategies include:

• Write-Through/Write-Invalidate: On a data update, the system writes to the primary source and simultaneously invalidates the corresponding entry in all caches.
• Time-To-Live (TTL): A passive policy where each cache entry has an expiration timestamp, after which it is considered invalid.
• Explicit Invalidation: The application or a backend service sends a signal (e.g., a pub/sub message) to all caching nodes to delete specific keys. Poor invalidation logic is a leading cause of coherence bugs, where agents act on outdated API responses.

A distributed cache is a network-based caching system where data is partitioned and replicated across multiple nodes. This architecture introduces the core challenge that cache coherence protocols solve. Key characteristics:

• Scalability: Capacity and throughput can be increased by adding more nodes.
• Fault Tolerance: Data replication prevents a single node failure from causing total cache loss.
• Shared State: Multiple agents or services can access the same cached data, making coherence critical. Examples include Redis Cluster and Memcached. In these systems, a coherence protocol like MESI or a directory-based protocol manages state transitions for each cache line across nodes.

The write-through pattern is a caching strategy that helps maintain strong consistency. When data is written, the operation completes only after updating both the cache and the primary data source (e.g., a database).

• Pros: Simplifies cache coherence because the cache always contains the latest data. Read operations are fast after a write.
• Cons: Write latency is higher, as it is bound by the slower of the two writes (cache and backend). This pattern is often contrasted with write-behind (asynchronous write) and is a foundational technique for ensuring an AI agent's tool-call results are immediately visible to other agents in the system.

The MESI protocol (Modified, Exclusive, Shared, Invalid) is a specific, widely implemented cache coherence protocol used in multi-core CPUs and analogous to distributed agent caches. It defines four states for a block of cached data:

• Modified (M): The cache line is dirty (changed) and is the only valid copy.
• Exclusive (E): The cache line is clean and is the only copy.
• Shared (S): The cache line is clean and may be duplicated in other caches.
• Invalid (I): The cache line is stale and cannot be used. Caches communicate via a coherence bus or interconnect to transition states, ensuring all observers see a single logical state. This is the mechanical blueprint for preventing race conditions in parallel agent execution.

Eventual consistency is a consistency model that is often contrasted with the strong guarantees provided by cache coherence protocols. It guarantees that if no new updates are made to a data item, eventually all accesses to that item will return the last updated value.

• Use Case: Ideal for high-throughput systems where absolute immediate consistency is not required, such as caching user profile data or product inventory counts.
• Mechanism: Achieved through asynchronous replication and anti-entropy processes that propagate updates in the background. In agent systems, using eventual consistency for certain non-critical caches (e.g., weather API results) can dramatically improve performance and availability, accepting a small window of staleness.