# How the Multi-Hop Retrieval Benchmark Measures Graph Performance vs. Grep Baseline

> Discover how the multi-hop retrieval benchmark evaluates graph performance against a grep baseline, measuring recall advantage and cost efficiency for your code review graphs.

- Repository: [Tirth Kanani/code-review-graph](https://github.com/tirth8205/code-review-graph)
- Tags: performance
- Published: 2026-08-16

---

**The multi-hop retrieval benchmark evaluates the Code Review Graph (CRG) by comparing its two-step traversal accuracy against a realistic grep-based baseline, quantifying recall advantage and cost efficiency through metrics like `neighbor_recall` and `score`.**

The **multi-hop retrieval benchmark** provides a rigorous, reproducible method for assessing how well graph-based code understanding systems handle complex, multi-step queries compared to traditional text search approaches. This benchmark, implemented in the `tirth8205/code-review-graph` repository, specifically targets the gap between simple keyword matching and relationship-aware code navigation.

## How the Benchmark Defines Multi-Hop Tasks

Each task in the benchmark simulates a realistic developer query requiring two logical steps. The task definitions live in YAML configurations under `code_review_graph/eval/configs/*.yaml` as specified in the repository's [REPRODUCING.md](/docs/REPRODUCING.md).

### Step 1: Anchor Discovery with Semantic Search

The first step uses **hybrid search** (semantic + lexical) to locate a starting node. The benchmark verifies that the returned node's qualified name ends with a specific suffix (`anchor_qualified_suffix`).

### Step 2: Single-Hop Traversal

From the discovered anchor, the benchmark invokes `query_graph` with a traversal pattern such as:

- `callers_of` – find functions that call the anchor
- `callees_of` – find functions called by the anchor
- `tests_for` – find test cases covering the anchor

This two-step pattern—**semantic search followed by structured traversal**—mirrors how developers actually explore unfamiliar codebases.

## Core Metrics in multi_hop_retrieval.py

The benchmark implementation in [[`code_review_graph/eval/benchmarks/multi_hop_retrieval.py`](https://github.com/tirth8205/code-review-graph/blob/main/code_review_graph/eval/benchmarks/multi_hop_retrieval.py)](/code_review_graph/eval/benchmarks/multi_hop_retrieval.py) collects five key metrics:

| Metric | Purpose |
|--------|---------|
| `anchor_found` | Boolean: was the correct anchor node returned? |
| `anchor_rank` | Position of correct anchor in results (0-indexed) |
| `neighbor_count` | Raw number of neighbors returned by traversal |
| `neighbor_recall` | Fraction of expected neighbors actually found |
| `score` | Combined metric: `int(anchor_found) * neighbor_recall` (range 0–1) |

The **score** metric penalizes complete failures heavily—if the anchor isn't found, the score is zero regardless of traversal quality.

## The Grep Baseline: agent_baseline.py

The baseline comparison is implemented in [[`code_review_graph/eval/benchmarks/agent_baseline.py`](https://github.com/tirth8205/code-review-graph/blob/main/code_review_graph/eval/benchmarks/agent_baseline.py)](/code_review_graph/eval/benchmarks/agent_baseline.py). This baseline simulates a **realistic "grep-and-read-top-k" agent**:

1. Executes pure-Python identifier-based grep on the query
2. Selects top-k files by relevance
3. Reads file contents for answer extraction

**Critical limitation**: The baseline performs only **one-hop** look-ups. It cannot follow chains of relationships (e.g., finding callers-of-callers) without additional iterative grep operations, each incurring file-system I/O costs.

## Performance Comparison: Where the Graph Wins

Running both benchmarks on identical curated repo configurations reveals two decisive advantages for the Code Review Graph:

### Recall Advantage on Chain Queries

Multi-hop queries often require following relationship chains. The graph resolves these via indexed edge traversals in `query_graph`, while the greedy grep baseline fails to surface intermediate nodes. Example results show the graph achieving **0.909 average score** versus approximately **0.5 for the baseline** on the same 11-task evaluation set.

### Cost Efficiency

- **Baseline**: Each hop requires file-system I/O and text parsing
- **CRG**: Traversals execute in-memory against pre-indexed relationships

This structural difference makes the graph approach fundamentally more scalable for deep code exploration.

## Running the Benchmark

### Programmatic Execution

```python
from pathlib import Path
from code_review_graph.eval.runner import run_all
from code_review_graph.store import Store

repo_path = Path("/path/to/checkout")
store = Store(repo_path)

config = {
    "name": "example-repo",
    "_embedding_provider": "openai",
    "_embedding_model": "text-embedding-ada-002",
    "multi_hop_tasks": [
        {
            "id": "t1",
            "nl_query": "Which functions call the `UserService.login` method?",
            "anchor_qualified_suffix": "UserService.login",
            "traversal_pattern": "callers_of",
            "expected_neighbor_names": [
                "AuthController.handleLogin",
                "AuditLogger.logLogin"
            ],
            "k": 10,
        },
    ],
}

from code_review_graph.eval.benchmarks.multi_hop_retrieval import run as mh_run
results = mh_run(repo_path, store, config)
print(results)

```

### CLI Execution

```bash
python -m code_review_graph eval --benchmark multi_hop_retrieval

```

The CLI delegates to [`code_review_graph/eval/runner.py`](https://github.com/tirth8205/code-review-graph/blob/main/code_review_graph/eval/runner.py), which loads YAML configs, builds the semantic store, and outputs CSV summaries to `evaluate/results/…_multi_hop_retrieval_*.csv`.

## Key Implementation Files

- **[multi_hop_retrieval.py](/code_review_graph/eval/benchmarks/multi_hop_retrieval.py)** – Core benchmark logic, metric computation
- **[agent_baseline.py](/code_review_graph/eval/benchmarks/agent_baseline.py)** – Grep-based baseline implementation
- **[runner.py](/code_review_graph/eval/runner.py)** – Benchmark orchestration and registration
- **[configs/*.yaml](/code_review_graph/eval/configs/)** – Per-repository task definitions
- **[docs/FEATURES.md](/docs/FEATURES.md)** – Benchmark results and graph advantage analysis
- **[docs/REPRODUCING.md](/docs/REPRODUCING.md)** – Complete reproduction instructions and schema documentation

## Summary

- The **multi-hop retrieval benchmark** uses curated two-step tasks to evaluate graph-based code search against realistic baselines
- **Score calculation** (`int(anchor_found) * neighbor_recall`) penalizes anchor discovery failures while rewarding traversal accuracy
- The **grep baseline** in [`agent_baseline.py`](https://github.com/tirth8205/code-review-graph/blob/main/agent_baseline.py) provides a strong but ultimately limited comparison point, topping out near 0.5 score versus the graph's 0.909
- **Indexed relationship traversal** enables both higher recall and lower operational cost for complex, multi-step queries
- All components are reproducible via the provided CLI and Python APIs in `tirth8205/code-review-graph`

## Frequently Asked Questions

### What makes the multi-hop retrieval benchmark different from standard code search benchmarks?

Standard benchmarks typically evaluate single-step retrieval: given a query, find relevant code snippets. The **multi-hop retrieval benchmark** specifically tests **chained reasoning**—combining semantic search with structured graph traversal to answer questions that require understanding relationships between multiple code entities, such as "which test files indirectly exercise this utility function through intermediate callers?"

### Why is the grep baseline considered "realistic" rather than naive?

The baseline in [`agent_baseline.py`](https://github.com/tirth8205/code-review-graph/blob/main/agent_baseline.py) is deliberately engineered to simulate actual developer tooling: it uses identifier-aware grep (not raw text search), ranks results by relevance, and limits itself to top-k file reads. This makes it **stronger than naive whole-corpus search** while still representing the fundamental limitation of text-based approaches—they cannot natively follow semantic relationships without expensive iteration.

### How does the `neighbor_recall` metric handle partially correct results?

`neighbor_recall` is calculated as the fraction of `expected_neighbor_names` present in the returned neighbor set. A value of 1.0 indicates perfect retrieval; 0.0 indicates complete failure. Partial credit applies proportionally—if 2 of 4 expected neighbors are found, recall is 0.5. This metric directly measures the graph's ability to resolve relationship traversals that the baseline cannot complete.

### Can I add custom multi-hop tasks for my own codebase?

Yes. Follow the schema in [docs/REPRODUCING.md](/docs/REPRODUCING.md) to define `multi_hop_tasks` in a YAML config under `code_review_graph/eval/configs/`. Each task requires `nl_query`, `anchor_qualified_suffix`, `traversal_pattern`, and `expected_neighbor_names`. The benchmark runner will automatically include your tasks in evaluation runs.