Multi-Hop Retrieval Without Runaway Latency

In a standard Retrieval-Augmented Generation (RAG) system, you retrieve documents, feed them to an LLM, and get an answer. It is linear. It is predictable. It is fast.

But real-world questions are rarely linear. Consider a user asking: "What was the impact of the 2023 API changes on the latency of the payment service, and how does that compare to the 2022 baseline?"

A single retrieval step will fail. The system must first find the 2023 API change notes, then retrieve the latency metrics for the payment service post-change, and finally retrieve the 2022 baseline metrics. This is multi-hop retrieval.

The naive implementation of this pattern is a performance nightmare. If each hop requires a vector search, an LLM call to synthesize the next query, and another vector search, the latency compounds. For three hops, you aren't just adding time; you are multiplying risk.

This article details how to manage this complexity without sacrificing response speed. We will implement hop budgets to constrain depth, parallel execution to collapse dependency trees, and streaming to mask computation time.

The Latency Trap: Why Sequential Chains Fail

Let’s look at the mechanics of a naive multi-hop chain. Imagine a system that uses an LLM to generate a follow-up query based on previous results.

# Naive Sequential Implementation
def naive_multi_hop(query, max_hops=3):
    current_query = query
    context = []
    
    for i in range(max_hops):
        # 1. Retrieve documents for current_query
        docs = vector_store.search(current_query)
        context.extend(docs)
        
        # 2. Ask LLM: "What do we still need to know?"
        next_query_prompt = f"""
        Based on {context}, what is the next specific question to answer?
        Original Query: {query}
        """
        response = llm.generate(next_query_prompt)
        current_query = response.text
        
        # 3. Wait for next iteration...
        if not current_query: break
        
    return llm.generate(f"Answer based on {context}")

In this flow, the total latency $T_{total}$ is:

$T_{total} = \sum_{i=1}^{N} (T_{retrieve} + T_{llm\_synthesis})$

If $T_{retrieve}$ is 200ms and $T_{llm\_synthesis}$ is 1.5 seconds, a 3-hop chain takes roughly 5.1 seconds. For an interactive application, this is unusable. Users expect responses under 2 seconds.

The problem isn't just the time; it's the serial dependency. The system cannot start hop 2 until hop 1 is fully complete. This is a classic bottleneck in distributed systems. Vector search latency adds up linearly because each step depends on the output of the previous one. Furthermore, LLM synthesis is often the primary bottleneck due to the computational cost of generating text token-by-token. In a sequential chain, these delays stack, creating a compounding effect that makes the system feel sluggish and unresponsive.

The Hop Budget Mechanism

To control latency, we must treat retrieval as a finite resource. We introduce the concept of a Hop Budget.

A hop budget is a hard limit on the number of retrieval steps allowed before the system must synthesize an answer, even if the information is incomplete. This prevents infinite loops and runaway costs.

Implementing the Budget

Instead of iterating indefinitely or relying on a soft max_hops, we track a budget counter. If the budget is exhausted, we force a synthesis step.

def budgeted_multi_hop(query, max_hops=2):
    budget = max_hops
    context = []
    current_query = query
    
    while budget > 0:
        docs = vector_store.search(current_query)
        context.extend(docs)
        
        # Check budget BEFORE generating next query
        budget -= 1
        
        if budget == 0:
            break # Force synthesis
            
        # Only ask for next query if we have budget left
        next_query = llm.generate(f"""
        Generate one more specific query to answer: {query}
        Current Context: {context}
        """)
        current_query = next_query
        
    return synthesize_answer(query, context)

By capping at 2 hops, we reduce worst-case latency to ~3.4 seconds. But we can do better.

The trade-off here is between recall and latency. A stricter budget might miss nuanced connections, reducing recall, but it guarantees a predictable response time. A hard limit is safer than a soft one in production environments because it prevents cascading failures where a single ambiguous query triggers an infinite loop of retrieval attempts, exhausting API quotas and server resources.

Parallel Dependency Resolution

Most multi-hop questions do not require strict serial dependencies. They require independent pieces of information that can be gathered in parallel.

Consider the question: "Who is the CEO of Company A, and what is their net worth?"

1. Hop 1: Find CEO of Company A.
2. Hop 2a: Find Net Worth of CEO.
3. Hop 2b: Find Recent News about CEO.

Steps 2a and 2b are independent. They do not depend on each other. In a sequential system, you wait for 2a to finish before starting 2b. In a parallel system, you fire both requests simultaneously.

Using Async/Await for Concurrency

Python’s asyncio allows us to launch multiple retrieval tasks concurrently. The key insight is that network I/O is non-blocking. While one request waits for the database, the CPU can process another.

import asyncio
import aiohttp
 
async def fetch_context(query):
    # Split query into independent sub-queries
    sub_queries = await llm.generate_async(f"""
    Break this query into independent sub-queries: {query}
    Return as JSON list.
    """)
    
    # Launch all retrievals concurrently
    tasks = [vector_store.search_async(q) for q in sub_queries]
    
    # Wait for ALL tasks to complete
    results = await asyncio.gather(*tasks)
    
    return flatten(results)
 
# Usage
context = asyncio.run(fetch_context("CEO net worth of Company A"))

This changes the latency profile from $T_1 + T_2$ to $\max(T_1, T_2)$. If both searches take 200ms, the parallel execution still takes 200ms, not 400ms.

However, error handling in async contexts is critical. If one sub-query fails (e.g., a timeout or a malformed response), the entire gather might fail unless configured otherwise. By using asyncio.gather(..., return_exceptions=True), you can catch individual task failures and decide whether to proceed with partial context or retry specific sub-queries. This resilience is essential for maintaining system stability under variable network conditions.

Streaming Responses: Masking Latency

Even with parallel retrieval, the final LLM synthesis step can take 1–2 seconds. Users will stare at a loading spinner. To improve perceived latency, we stream the response.

Streaming works by sending tokens to the client as soon as they are generated, rather than waiting for the entire response. This reduces Time to First Byte (TTFB) to near zero.

Implementing Server-Sent Events (SSE)

In a web backend, you can use Server-Sent Events to stream the LLM output incrementally.

from fastapi import FastAPI
from fastapi.responses import StreamingResponse
 
app = FastAPI()
 
async def stream_response():
    # Start retrieval (parallel)
    context = await fetch_context("CEO net worth of Company A")
    
    # Stream LLM generation
    async for chunk in llm.stream_async(f"Answer: {context}"):
        yield f"data: {chunk}\n\n"
 
@app.get("/stream")
async def stream():
    return StreamingResponse(stream_response(), media_type="text/event-stream")

The client receives the first token almost immediately, creating the illusion of instant response. The user sees the text appearing character by character, which feels faster than waiting for a full block.

On the client side, handling this stream typically involves using the EventSource interface in JavaScript or a custom fetch loop with a ReadableStream reader. SSE is unidirectional, meaning data flows only from the server to the client, which is perfect for LLM outputs. Unlike WebSockets, SSE is simpler to implement and automatically handles reconnection logic, making it ideal for streaming generation tasks.

Trade-offs and Opinions

Implementing parallel multi-hop retrieval introduces complexity. You must handle:

1. Error Propagation: If one parallel task fails, do you retry? Do you proceed with partial context?
2. Cost Management: Parallel retrieval increases API calls. If you split one query into 5 sub-queries, you pay for 5 retrievals instead of 1.
3. Context Window Limits: Aggregating results from parallel hops can exceed the LLM’s context window. You must implement aggressive summarization or chunking.

Opinion: Do not over-engineer the parallelism. Most questions only have 1–2 independent hops. If you are splitting queries into 10+ sub-queries, you likely have a poorly structured prompt or a fragmented knowledge base. Start with a hop budget of 2, use parallel execution only for clearly independent sub-queries, and stream everything.

For deeper insights on latency management, refer to the FastAPI documentation on StreamingResponse and the Python asyncio documentation on gather. Industry benchmarks often cite that perceived latency improvements via streaming can meaningfully reduce user abandonment rates (Source: Nielsen Norman Group).

Common Pitfalls

1. Over-splitting queries: Breaking a query into too many sub-queries can lead to redundant retrievals and wasted cost. Ensure sub-queries are truly distinct.
2. Ignoring error propagation: Failing to handle exceptions in parallel tasks can cause the entire request to fail silently or crash the service. Always use return_exceptions=True in asyncio.gather.
3. Context window overflow: Aggregating results from multiple parallel hops can quickly exceed the LLM's context window. Implement summarization or prioritization strategies to keep context manageable.

Practical Takeaways

1. Parallelize independent hops: Identify parts of the query that don't depend on each other and execute them concurrently.
2. Stream everything: Use SSE or WebSockets to send tokens as they are generated, improving perceived performance.
3. Budget strictly: Set hard limits on the number of hops to prevent runaway costs and infinite loops.

FAQ

How do I handle partial failures in parallel retrieval? Use asyncio.gather(..., return_exceptions=True) to catch individual task failures. You can then filter out exceptions and proceed with the successful results, or implement a retry mechanism for specific failed sub-queries.

Is SSE better than WebSockets for this use case? For LLM streaming, SSE is generally preferred because it is simpler, unidirectional, and handles reconnections automatically. WebSockets are bidirectional and more complex, making them overkill unless you need real-time two-way communication.

How do I decide the optimal hop budget? Start with a budget of 2-3 hops. Monitor the success rate of answers versus the cost and latency. If users frequently ask questions that require more than 3 hops, consider refining your indexing strategy or using a more powerful LLM for query decomposition.