How BFS and DFS Graph Traversal Work with Token Budgets in code‑review‑graph

The code‑review‑graph extension implements BFS traversal with a configurable depth limit that acts as a token budget, ensuring that sub‑graphs sent to LLM features remain within predictable size constraints by capping the number of hops explored from a selected node.

The code‑review‑graph VS Code extension constructs an in‑memory code‑dependency graph where SimNode objects represent symbols (classes, functions) and SimLink objects represent relationships (imports, extends, calls). When analyzing complex codebases, the system must prevent runaway context growth that would overwhelm LLM token limits, which is why the traversal uses a strict hop‑based budgeting system rather than literal token counting.

BFS Traversal with Depth‑Limited Token Budgets

The primary traversal mechanism uses Breadth‑First Search (BFS) constrained by a configurable depth limit that functions as the token budget. In src/webview/graph.ts, the getVisibleData() function implements this logic by expanding the frontier one hop at a time until reaching the configured limit.

The algorithm initializes a reachable set containing the selected node's qualified name, then iterates through depth levels:

// src/webview/graph.ts – BFS core (lines 94-126)
if (selectedNode && depthLimit > 0) {
  const reachable = new Set<string>();
  reachable.add(selectedNode.qualifiedName);
  let frontier = new Set<string>([selectedNode.qualifiedName]);

  for (let d = 0; d < depthLimit; d++) {
    const next = new Set<string>();
    for (const qn of frontier) {
      for (const link of links) {
        const srcQn = typeof link.source === "object"
          ? (link.source as SimNode).qualifiedName
          : link.sourceQualified;
        const tgtQn = typeof link.target === "object"
          ? (link.target as SimNode).qualifiedName
          : link.targetQualified;

        if (srcQn === qn && !reachable.has(tgtQn)) {
          reachable.add(tgtQn);
          next.add(tgtQn);
        }
        if (tgtQn === qn && !reachable.has(srcQn)) {
          reachable.add(srcQn);
          next.add(srcQn);
        }
      }
    }
    frontier = next;
    if (frontier.size === 0) break;
  }
  nodes = allNodes.filter(n => reachable.has(n.qualifiedName));
}

Each iteration of the d loop represents one hop through the dependency graph. When depthLimit is reached, the traversal stops, regardless of unexplored nodes. This hard cutoff ensures that the resulting sub‑graph contains a predictable maximum number of nodes and edges.

UI Controls for Token Budget Management

Users interact with the token budget through a depth slider in the Webview interface. The slider updates the depthLimit variable, which triggers a fresh BFS execution via buildGraph():

// UI control implementation (graph.ts)
const depthSlider = document.getElementById("depth-slider") as HTMLInputElement;
depthSlider.addEventListener("input", () => {
  depthLimit = Number(depthSlider.value);   // token-budget = max hops
  const depthValue = document.getElementById("depth-value");
  if (depthValue) depthValue.textContent = depthSlider.value;
  buildGraph();                             // re-run BFS with new budget
});

Changing the slider value immediately recalculates the visible graph, allowing users to visually preview how much context they are including before invoking LLM‑powered features.

Backend Impact Radius and DFS Support

While the UI implements explicit BFS, the backend in src/backend/sqlite.ts supports both traversal directions through the impactRadius() function. This function runs a BFS forward and backward up to the configured depth, as noted in the source comments:

// src/backend/sqlite.ts (line 13)
*  4. Runs a BFS impact radius query up to the configured depth.

The backend implementation can accommodate DFS‑style traversal by modifying the frontier expansion order (using a stack instead of a set), though the current UI defaults to BFS for predictable breadth‑wise exploration:

// src/backend/sqlite.ts – impact radius implementation
export function impactRadius(startQn: string, maxDepth: number): Promise<GraphSlice> {
  // Runs a BFS forward + backward up to `maxDepth` hops.
  // The `maxDepth` parameter is the same "token budget" used by the UI.
  // ...
}

The blastRadius.ts feature file exposes this backend capability to the VS Code command palette, allowing users to compute impact radii programmatically while respecting the same depth constraints.

Token Budget Safety for LLM Integration

The token budget mechanism ensures that downstream LLM features receive only manageable context windows. When the user triggers a review or explanation feature, the limited sub‑graph is serialized and passed to the LLM client:

// src/features/reviewAssistant.ts
const subGraph = await backend.getImpactRadius(node.qualifiedName, depthLimit);
// `subGraph` is guaranteed to stay under the token budget, so the LLM request
// will not exceed the model's token limits.
await llmClient.generateExplanation(subGraph);

This workflow prevents the common failure mode of accidentally sending thousands of lines of transitive dependencies to an LLM. By treating graph hops as a proxy for token consumption, the system provides intuitive user control while maintaining technical safety.

Summary

• BFS with depth limits: The getVisibleData() function in src/webview/graph.ts implements level‑by‑level BFS that stops after depthLimit iterations, treating the limit as a token budget.
• Hop‑based budgeting: The system uses graph depth rather than literal token counting, with each hop potentially adding nodes and edges that translate to LLM tokens.
• UI integration: The depth slider provides real‑time control over the budget, immediately re‑running traversal via buildGraph() when adjusted.
• Backend support: The impactRadius() function in src/backend/sqlite.ts provides backend BFS traversal that respects the same depth constraints, supporting both forward and backward graph exploration.
• LLM safety: Serialized sub‑graphs from reviewAssistant.ts and blastRadius.ts use these budget constraints to guarantee context window compliance.

Frequently Asked Questions

What exactly is the token budget in code‑review‑graph?

The token budget is implemented as a configurable depth limit on graph traversal rather than a literal character or token counter. Each hop in the dependency graph potentially adds code symbols (nodes) and relationships (edges) that would increase the context size sent to LLM features. By capping the BFS depth, the system ensures the serialized sub‑graph remains within predictable size constraints that map to LLM token limits.

How does the depth slider control token usage?

The depth slider in the Webview directly sets the depthLimit variable used by the BFS algorithm in getVisibleData(). When you increase the slider value, the traversal explores more hops from the selected node, including more symbols in the result. This linearly increases the amount of context data that will be serialized and sent to LLM services, making the slider an intuitive proxy for "how much context to include."

Can I use DFS instead of BFS for graph traversal?

While the current UI implements BFS for predictable breadth‑wise exploration, the underlying traversal logic in src/backend/sqlite.ts can support DFS by swapping the frontier data structure from a set to a stack. The impactRadius() backend function handles the traversal mechanics and could be modified to use depth‑first ordering, though the default BFS approach is preferred for code review scenarios where understanding immediate neighbors (breadth) is typically more valuable than deep call chains (depth).

How does the token budget prevent LLM context overflow?

The token budget prevents overflow by guaranteeing a maximum subgraph size before any LLM API call occurs. When features like reviewAssistant.ts request an impact radius, they pass the depthLimit to getImpactRadius(), which returns only nodes reachable within that many hops. This bounded result set is then serialized to JSON, ensuring that even in dense codebases with thousands of dependencies, the extension cannot accidentally transmit unbounded context that would exceed model token limits or incur excessive API costs.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}