CONCORD: Asynchronous Sparse Aggregation for Device-Cloud RAG under Document Isolation

Technical Summary: CONCORD

Problem Statement
The paper addresses the challenge of Retrieval-Augmented Generation (RAG) in a device-cloud collaborative setting where documents are isolated between the two ends. In this "document-isolated dual-end RAG" scenario, private documents reside on the edge device while public knowledge resides in the cloud. Privacy and policy constraints forbid the exchange of raw documents between the two sides.

Existing approaches to this problem face significant limitations:

1. Centralized Transfer: Transferring remote documents or representations to one side often incurs growing communication overhead or requires rebuilding prefix-dependent states.
2. Dense Synchronization: Methods that keep both sides jointly involved (e.g., DRAGON) typically rely on frequent remote synchronization and dense evidence transfer (e.g., full KV states or score vectors) at every decoding step. This creates bottlenecks in throughput and latency under realistic network conditions, as the local side must frequently wait for remote participation or handle rollbacks when remote drafts are rejected.

The core problem is how to coordinate retrieval and generation across isolated ends to minimize system cost (latency and bandwidth) while preserving the exactness of the aggregated output distribution.

Methodology: CONCORD
The authors propose CONCORD, an asynchronous sparse aggregation framework that treats the cloud not as a continuously synchronized co-generator, but as an asynchronously arriving source of evidence. The framework decouples the decision of when to consult the cloud from how much evidence to transfer. It introduces two coupled mechanisms:

1. Waiting Debt Control (Temporal Sparsification):

   • Mechanism: Instead of keeping the remote side on the critical path at every step, CONCORD uses a lightweight "debt queue" to track the observed return of remote participation.
   • Logic: If a decoding step times out or if remote evidence is frequently rejected (indicating the local decision is robust), the system accumulates "debt." When debt exceeds a threshold, the controller shortens the waiting budget for subsequent steps, allowing the device to commit locally without waiting for the cloud.
   • Goal: To suppress low-return waiting and reduce the frequency of remote participation, thereby removing the remote side from the critical path when local evidence is sufficient.

2. Certificate-Guided Minimal Supplementation (Communication Sparsification):

   • Mechanism: When a step does consult the cloud, CONCORD avoids transferring full remote evidence. Instead, it uses an upper-bound certificate to determine the minimal evidence required to confirm the current greedy token.
   • Logic: The system first checks if the current local candidate is already "certified" (i.e., its aggregated score is provably higher than any possible score of unrevealed remote candidates). If not, it requests only the specific "ambiguity-critical" token IDs or sparse chunks necessary to resolve the decision.
   • Goal: To reduce the communication payload per consultation by transmitting only the evidence needed to overturn or confirm the greedy decision, scaling with residual ambiguity rather than vocabulary size.

Key Contributions

1. Formulation: The paper formulates dual-end RAG under document isolation as a joint minimization of generation loss and interaction cost across two dimensions: the temporal frequency of remote participation and the per-consultation communication payload.
2. Framework: It introduces CONCORD, which reformulates the cloud as an asynchronous evidence source, enabling sparse remote participation while maintaining exact output aggregation on consulted steps.
3. Mechanisms: It designs the Waiting Debt Control (O(1) complexity per token) and Certificate-Guided Minimal Supplementation, which together decouple temporal and communication decisions.
4. Evaluation: The framework is evaluated on Natural Questions (NQ) and WikiText-2, demonstrating significant efficiency gains without compromising answer quality.

Experimental Results
Experiments were conducted on both single-machine (controlled) and real two-machine deployments using the Qwen3-1.7B model.

• Throughput: CONCORD improved end-to-end throughput by 1.66× on Natural Questions and 2.15× on WikiText-2 compared to the state-of-the-art baseline, DRAGON.
• Communication: Per-token communication was reduced by over two orders of magnitude (approx. 99.9% reduction), dropping from ~250KB/token to ~280 bytes/token on NQ and ~160 bytes/token on WikiText-2.
• Quality: The framework maintained answer quality (F1 and Exact Match on NQ) and perplexity (on WikiText-2) comparable to dense aggregation baselines (DRAGON and DRDG/TW).
• Ablation: Removing either the waiting control or the communication control resulted in suboptimal performance, confirming that both mechanisms are necessary to achieve the full efficiency gains.
• Robustness: The performance advantages persisted under varying network conditions, including injected delay and jitter in a two-machine deployment.

Significance and Claims
The paper claims that CONCORD bridges the gap between centralized RAG methods, edge-cloud collaborative systems, and speculative decoding by introducing a sparse, asynchronous remote participation model. Its significance lies in demonstrating that:

• Remote participation does not need to be continuous or dense to achieve exact dual-end aggregation.
• By treating the cloud as an asynchronous source and using debt-based waiting and certificate-guided supplementation, systems can drastically reduce latency and bandwidth costs.
• The approach preserves the exactness of the greedy decision on steps where consultation occurs, ensuring that the quality of the generated text remains on par with fully synchronized methods.

The authors note that the current study is limited to greedy decoding in a two-end setting with a single model, but suggest the asynchronous sparse participation model could apply to other collaborative inference services with variable remote evidence delays.