Coding Speculative Retrieval Against Stragglers While the User Is Still Talking

Voice assistants now start their work before the user finishes speaking. Systems such as Stream RAG send search queries built from the partial sentence heard so far, so that retrieved documents are already available when the user stops. When the document index is too large for one device and is split across several machines (shards), a single slow machine, called a straggler, delays the final answer. The system cannot rank documents until every shard has scored the query. This note proposes a fix that relies on a property only incremental speech has: the query issued at the end of an utterance is usually a small edit of a query the system already scored a second earlier.

The proposal has two parts. First, the index shards are stored with erasure-style redundancy. This is coded computing: machines hold linear combinations of shards, so the full result can be rebuilt from any sufficiently large subset of them. Second, the decoder uses the previous speculative query's scores as prior information. When fewer machines than the exact recovery threshold have replied, the master solves only for the change in scores since the last query, and that change is small whenever the utterance has stabilized. The expected result is that end-of-utterance retrieval stops waiting on the slowest shard, returns exact results when enough machines reply, and degrades in proportion to how much the question changed when they do not.

Core Claim

Dense retrieval scores a query embedding $q$ against a document matrix $A$ by computing $s = Aq$, a large linear transform. Coded methods for linear transforms already exist: Short-Dot splits $y=Ax$ into redundant short dot products, and MDS-coded inference in CoCoI decodes from any $k$ of $n$ edge workers. Both treat every job as a one-shot event with no history. Incremental speech gives the master a history for free: exact or near-exact scores $s_{t-1} = Aq_{t-1}$ for the previous prefix query.

Split $A$ into $K$ row blocks and store $N>K$ coded blocks built from a generator $G$. At query $t$, a subset $R$ of workers returns $y_R = G_R z_t$, where $z_t$ stacks the true block scores $Aq_t$ and $G_R$ holds the generator rows of the responders. The master then decodes relative to the prior:

$$\hat z_t = s_{t-1} + G_R^{+}\,(y_R - G_R s_{t-1}), \qquad \|\hat z_t - z_t\| = \|(I - G_R^{+}G_R)\,A(q_t - q_{t-1})\| \le \|A(q_t-q_{t-1})\|,$$

where $G_R^{+}$ is the pseudo-inverse. The error expression follows because $y_R - G_R s_{t-1} = G_R A(q_t-q_{t-1})$ exactly. What remains is the part of the score change that the responders cannot see. Three cases follow. With $|R|\ge K$ the decode is exact, as in ordinary MDS coding. With fewer responders, the error is bounded by the query drift rather than by the size of the missing shard. The pseudo-inverse over a small, well-chosen $G_R$ also avoids the large ill-conditioned Vandermonde inversions that the coded-computing literature flags as a failure mode (On the Optimal Recovery Threshold of Coded Matrix Multiplication).

A second benefit comes from late replies. A straggler's reply for round $t-1$ that arrives during round $t$ is not wasted: it tightens $s_{t-1}$ and therefore the prior. This partly addresses the "work erasure" problem, in which late partial work is normally thrown away.

Relation to Prior Work

Three papers supply the method. Short-Dot and CoCoI supply coded linear transforms and the shift-exponential straggler model. ε-approximate MatDot shows that tolerating small error nearly halves the number of workers needed. That result is the reason to expect approximate decoding to pay off for ranking, which only needs the top-$k$ order to be preserved.

Two papers are the closest prior art on coding over time or approximately. Coded Sequential Matrix Multiplication interleaves consecutive independent jobs so that job $i$ may finish by round $i+T$. It treats jobs as unrelated and allows extra delay. We instead exploit the fact that consecutive jobs are near-duplicates, and we allow no extra delay for the final query. LeTCC regresses missing worker outputs with smoothing splines across workers. Our prior runs across time, not across the worker index. LeTCC was evaluated only on batch image classification.

On the speech side, Stream RAG motivates the problem. It hides retrieval behind user speech but notes heavy parallel-query overhead, and it has no handling for shard tail latency. Can Speech LLMs Think while Listening? supplies a question-completeness signal ($\zeta$, based on KL divergence) that we reuse to predict drift. One source constrains the design. Audio MultiChallenge finds that mid-utterance self-corrections ("Boston—no, Denver") are the weakest axis for current models. Those are exactly the cases where drift is large and the temporal prior should help least, so the method must detect them and fall back to waiting.

Research Program

We will build a sharded exact dense-retrieval service over the document collection behind AudioCRAG. It will run on two platforms: a simulated cluster with injected delays drawn from shift-exponential and bursty Fritchman models, matching the models used by CoCoI and DIP, and a small physical Raspberry Pi cluster modeled on CoCoI's 11-node WiFi testbed.

In front of the service sits a cascaded incremental pipeline. It takes partial ASR hypotheses from the human recordings in AudioCRAG, rewrites them into queries at Stream RAG-style fixed intervals, and embeds them. Stream RAG's own model may not be available, so we reproduce its fixed-interval trigger rather than its end-to-end model.

The master implements the prior-anchored decoder and a stopping rule. At end of utterance, it waits until either $K$ coded replies arrive or the predicted drift bound $\|A(q_t-q_{t-1})\|$ falls below a ranking margin. The bound is estimated from $\|q_t-q_{t-1}\|$ and a spectral-norm estimate of $A$, and it is gated by $\zeta$.

On the analysis side, we will state the ranking-preservation condition: top-$k$ order is exact when the decoding error is below half the score gap at rank $k$. We will then measure how often real utterances satisfy it, and stratify the results by utterances with and without self-repairs.

Baselines

The naive reference is synchronous uncoded retrieval: $K$ plain shards, where the master waits for all of them. This is what a straightforward sharded Stream RAG deployment does. CoCoI reports that uncoded execution sees latency spikes of nearly 80% under induced slowdowns, so we expect this baseline to show the tail problem clearly.

The second baseline drops stragglers. It ranks documents from whichever uncoded shards return by the deadline and treats the missing shards as empty.

The strongest practical competitor is hedged replication. Each shard is stored on $r$ machines, and the master takes the first copy to reply. It is simple, it is what production systems do, and it needs no decoding. It will be run at the same storage redundancy $N/K$, the same per-worker compute, and the same delay distributions as our method.

The strongest coded competitor is plain MDS decoding in the style of CoCoI and Short-Dot. It uses the same generator but no temporal prior, and it waits for $K$ replies. We also run DIP-style sequential coding with its delay parameter set so that the final query is due at end of utterance.

The key ablation is replication plus stale fill-in. Missing shards are filled with their previous-query scores, with no coding. This isolates whether the gain comes from the temporal prior alone or from combining it with coding.

All methods share the same index, encoder, trigger schedule, delay seeds, and tuning budget. The stopping thresholds for every method are tuned on the same held-out split.

There is no reported result on Lacuna for straggler-resilient speculative retrieval in spoken dialogue, so no baseline number exists for this exact question. The nearest reported numbers are CoCoI's average latency reduction of up to 34.2% over uncoded inference, with 2–9% encode/decode overhead, on VGG16 and ResNet18. DIP and IDIP report 36% and 41% processing-time reductions over polynomial codes. Beating the baselines means two things. First, the method must match the recall@10 of synchronous exact retrieval while cutting 95th-percentile end-of-utterance retrieval latency relative to both hedged replication and plain MDS at equal redundancy. Second, it must preserve Stream RAG's downstream AudioCRAG accuracy gain, which was reported as 20.0% absolute over closed-book.

Why not just…?

Why not just hedge requests by replicating shards? This is the real threat. With few workers and independent delays, 2× replication can be close to 2× MDS redundancy in tail latency. The file's evidence against replication is its waste and its vulnerability when copies straggle together under bursty delays (Algebraic redundancy summary), and that evidence is not specific to speech. The experiment settles it by comparing the methods at matched redundancy under both independent and bursty delays. The replication-plus-stale-fill-in ablation matters most here. If it matches the full method, the honest conclusion is that the temporal prior is the contribution and coding is unnecessary, and we would report it that way.

Why not just drop straggling shards and rank what came back? Losing $S$ of $K$ shards removes roughly an $S/K$ fraction of candidate documents. LeTCC's results argue that uncontrolled omission gives arbitrary rather than bounded error. For single-answer factual QA such as AudioCRAG, a missing gold passage is a wrong answer. We measure recall loss and QA accuracy directly. If the relevant documents turn out to be redundantly present across shards, dropping could be competitive, and the data will show it.

Why not just keep the whole index on one fast server? If the index fits on one machine that never straggles, the problem vanishes, and we concede that regime. Our target regime is wearable and edge-cluster deployments and sharded cloud search, where Stream RAG already reports overhead pressure. Even there, we will report the index size at which single-node brute force becomes slower than distributed coded retrieval on the Pi testbed.

Proposed Experiments

The first experiment is the latency–recall trade-off. On AudioCRAG, using its human recordings for real speech timing, and on SLUE-SQA, we plot recall@10 at end of utterance against 50th- and 95th-percentile retrieval completion time for every baseline. The sweep covers straggler rates and both delay models, with $N/K \in \{1.25, 1.5, 2\}$. A decisive positive result is exact-level recall with fewer than $K$ replies on most utterances, together with a lower tail than both hedging and plain MDS.

The second experiment tests the error bound. We stratify utterances by measured final-step drift $\|q_t-q_{t-1}\|$ and by the presence of self-repairs. The prediction is that the decoding error tracks the bound in the Core Claim, and that on repairs the stopping rule falls back to waiting rather than returning wrong rankings. If rankings break on low-drift utterances, the mechanism is wrong.

The third experiment is end-to-end. We plug the service into the cascaded Stream RAG-style pipeline and report QA accuracy and first-token latency under injected stragglers. The references are Stream RAG's reported 3.16 s to 1.36 s first-token latency and its SLUE-SQA exact match of 55.8% at −0.68 s. The success criterion is that straggler injection no longer erases the latency advantage of streaming retrieval.

The fourth experiment measures master overhead on the Pi cluster, where the prior-anchored pseudo-inverse is only $|R|\times K$. The target is decoding cost in CoCoI's reported 2–9% range.