Breadth-First Search (BFS) is a graph traversal algorithm that explores nodes level by level, processing all neighbors at the current depth before moving deeper. BFS history has been a fixture of computer science education for decades.
What has changed is where it shows up. Today, BFS appears in LLM reasoning frameworks such as Tree of Thoughts (NeurIPS 2023) and in other search-based reasoning setups, though it is not generally used or referred to as the routing mechanism in typical knowledge-graph-grounded agent retrieval systems or multi-agent tool routing architectures.
TL;DR BFS explores graphs level by level using a queue, guaranteeing completeness and shortest paths in unweighted graphs. In modern AI systems, BFS appears in reasoning frameworks and knowledge graph retrieval as multi-hop traversal. BFS is often the better choice for shallow, broad exploration, while DFS is better for deeper, more memory-efficient traversal along a single path. BFS's main limitation in AI is exponential frontier growth, which increases token, API, and compute costs unless bounded by depth, beam limits, or stopping rules. How Does Breadth-First Search Work? BFS operates on graph-shaped data: nodes connected by edges. This structure also shows up in graph databases , social networks, knowledge graphs , and organizational hierarchies. The algorithm starts at a source node and visits every reachable node one level at a time.
The Queue Mechanic BFS uses a queue, a first-in, first-out (FIFO) data structure, to control the order of exploration. The source node enters the queue first. At each step, BFS removes the front node from the queue, marks it as visited, and enqueues all its unvisited neighbors.
Because BFS adds neighbors to the back and processes from the front, every node at depth 1 is visited before any node at depth 2. Every node at depth 2 is visited before any node at depth 3. This level-by-level discipline is what sets BFS apart from other traversal strategies.
Consider an agent that starts at a customer entity and needs to gather all related records. BFS first visits the customer node, then enqueues all first-degree connections: the deal, the support ticket, the invoice. Only after processing all three does it move on to second-degree connections, such as the sales rep linked to the deal.
Completeness and Shortest-Path Guarantee BFS provides two guarantees that matter for AI systems. First, completeness: if a path exists between the source and any target node, BFS will find it. Second, shortest path: in an unweighted graph, where all edges have equal cost, BFS always discovers the path with the fewest hops. These guarantees hold because BFS covers each depth level before moving on.
The Space-Complexity Tradeoff The time complexity of BFS is O(V + E), where V is the number of vertices and E is the number of edges. Space complexity is the constraint that matters: O(b^(d+1)), where b is the branching factor, or average number of neighbors per node, and d is the depth of the shallowest goal.
That exponent is not just a textbook abstraction. A graph with a branching factor of 10 produces 10 frontier nodes at depth 1, 100 at depth 2, and 1,000 at depth 3. BFS must hold all frontier nodes in memory simultaneously. In classical computing, this is a RAM problem. In AI agent systems, each frontier node translates to tokens, API calls, or compute cycles. So space complexity quickly becomes a billing problem.
How Do BFS and DFS Compare? BFS and Depth-First Search (DFS) are the two foundational graph traversal strategies. DFS uses a stack, or last-in, first-out data structure, instead of a queue. It follows a single branch as deep as possible before backtracking. The choice depends on the structure of your graph, what you're searching for, and how you're paying for computation.
Property BFS DFS Data structure Queue (FIFO) Stack (LIFO) Traversal order Level by level (all neighbors first) Branch by branch (deepest node first) Shortest path guarantee Yes (unweighted graphs) No Completeness Yes (always finds a solution if one exists) Yes only on finite graphs; may loop on infinite graphs Worst-case time complexity O(b^(d+1)) where b = branching factor, d = depth of shallowest goal O(b^m) where m = maximum depth Space complexity O(b^d), stores the frontier in the worst case O(bd), stores the current path with pending siblings Best fit (AI agent context) Broad fact-gathering across many sources at shallow depth Deep causal reasoning following a single chain of relationships
How Do You Choose BFS, DFS, or a Hybrid? The right traversal depends on the query shape. BFS fits broad fact-gathering at shallow depth, for example, "show me everything connected to this customer" , while DFS fits deep causal reasoning that follows a single chain through many hops, such as "trace the approval path for this budget request." A peer-reviewed clinical GraphRAG study (Hu et al., 2025) illustrates this split, routing fact and symptom queries to BFS at shallow depth (k=2) and causal, multi-hop queries to DFS at k=3-4.
When you need BFS's completeness and shortest-path guarantees without its memory cost, Iterative Deepening DFS (IDDFS) is the hybrid. It runs DFS repeatedly with increasing depth limits, using DFS-level memory while achieving BFS-level coverage. The tradeoff is repeated work at shallow nodes: modest overhead relative to the memory savings when branching factors are large.
Where Does BFS Appear in Modern AI Systems? Teams that build AI agents often implement BFS-class traversal patterns without using the term. LangGraph documentation describes "fan-out" and "supersteps." Anthropic's engineering blog discusses "spawning subagents" that "explore different aspects simultaneously." OpenAI's developer cookbook covers "multi-hop retrieval."
Each of these maps to BFS's level-by-level frontier expansion. Context engineering patterns frequently rely on BFS operations under different names.
AI System Area What BFS Does Example Key Constraint LLM reasoning frameworks (Tree of Thoughts) Explores candidate reasoning paths breadth-first at each step ToT-BFS evaluates b states per level with configurable depth Token cost scales exponentially with branching factor Knowledge graph agent retrieval Traverses relationships outward from a query entity to gather context Clinical GraphRAG uses BFS at depth k=2 for fact queries Graph density and depth affect API calls and latency Multi-agent tool routing Matches a query to the right agent-tool path Agent-as-a-Graph routes from query to executable tool chain Routing overhead scales with registered agents and tools
LLM Reasoning Frameworks The Tree of Thoughts framework runs a BFS-style search with three parameters: b states retained per step, T steps, and k thoughts generated per state. At each step, the model proposes candidates, evaluates them globally, and keeps the top-b. On Game of 24 with GPT-4, ToT at b=5 hit 74% success versus 7.3% for standard prompting, essentially a width-bounded beam search rather than exhaustive BFS.
Variants take different paths. LATS (ICLR 2024) swaps BFS for MCTS with UCB-guided selection. Thought of Search (NeurIPS 2024) has the LLM generate successor and goal functions once, then runs a classical BFS engine without further model calls.
Knowledge Graph Agent Retrieval Graph traversal extracts context from knowledge graphs in agentic retrieval patterns . The clinical GraphRAG study selects BFS at depth k=2 for factual queries like "What condition is entecavir indicated for?" and DFS at k=3-4 for causal chains.
StepChain GraphRAG uses BFS to expand along relevant edges per sub-question, assembling explicit evidence chains. GraphAgents deploys BFS as a callable agent tool alongside other strategies, including a "BFS with Semantic Stop" variant that halts when semantically relevant nodes are found rather than exhausting the depth limit.
Multi-Agent Tool Routing Agent-as-a-Graph tackles a different problem: routing a user query to the right agent-tool combination. The framework uses knowledge graph traversal and weighted reciprocal rank fusion to match queries to executable tool chains. As more agents and tools are registered, efficient routing becomes a meaningful constraint on latency and accuracy.
In production environments, this routing layer often sits alongside infrastructure such as Agent MCP , which gives an AI agent a single place to access business data and tools instead of wiring separate endpoints into every workflow. Developer teams that want to script or embed these retrieval and action patterns programmatically can also work through an Agent SDK , rather than rebuilding traversal-aware integrations from scratch.
Why Does BFS's Space Cost Matter for AI Agents? BFS's O(b^d) space growth is a well-known theoretical property. In LLM agent systems, this becomes a concrete budget problem: each frontier node represents an active trajectory state that requires at least one API call to carry the full conversation history.
The Tree of Thoughts paper provides direct cost data . On Game of 24 with GPT-4, ToT-BFS (b=5) cost $0.74 per case versus $0.13 for single-path prompting, approximately 5× the token spend at fixed depth. A web agent ablation measured the scaling across depth: at b=5, the theoretical frontier grows from 5 nodes (d=1) to 3,125 nodes (d=5), with only a modest improvement in success rate.
The cost compounds because each node at depth d carries the full conversation history of its trajectory. So cost per node grows with depth, not just with the number of nodes. Tree-of-Thought methods can become impractical without pruning when the action space is large.
How Do Airbyte Agents Handle Cross-System Context Retrieval? When agents need to reason across multiple SaaS sources at query time, each source adds API calls, pagination, and token overhead. That is the same runtime assembly problem that makes breadth-first exploration expensive in many production systems.
Airbyte Agents is the context layer for AI agents. It addresses this by pre-materializing data from connected sources into a managed, searchable index that agents query directly rather than crawling upstream APIs. Agents answer filtered lookups from indexed context rather than running live traversals across every connected system.
Agents need better context to produce better results. Refreshes can happen on a schedule, with direct API fallback available for live lookups and state-changing operations.
Ready to Cut the Cost of Multi-Source Agent Queries? BFS provides two properties that production AI systems need: completeness, meaning it always finds a path if one exists, and shortest-path guarantees in unweighted graphs. Its primary cost, exponential space growth, maps directly to token consumption and API call counts in agent architectures.
In practice, BFS has moved from a textbook algorithm to an engineering parameter. ToT-BFS exposes branching factor, depth, and evaluation count as tunable settings. Clinical GraphRAG systems may use query routing or dynamic tool selection to choose among retrieval methods based on the query. Production systems use beam limits and semantic stopping to control cost.
Whether you're tuning beam widths in a reasoning framework or bounding depth in a knowledge graph agent, the underlying challenge is the same: keeping cross-system context cheap enough to reach at runtime. Airbyte Agents reduce the need for runtime traversal across enterprise data sources by pre-materializing cross-system context into a single queryable store. That store is the Context Store , a managed, searchable index that lets agents query prepared business context directly instead of crawling upstream systems at request time. This shifts work out of the runtime path, helping reduce latency, token consumption, and context bloat in multi-source agent workflows.
Get a demo to see how Airbyte Agents reduces token and API costs for multi-source agent queries, or try Airbyte Agents today.
FAQs Is BFS or DFS better for AI agents? Neither is universally better. BFS suits broad fact-gathering at shallow depth, where you need to collect context from many related entities. DFS suits deep causal reasoning that follows a single chain of relationships through many hops.
Does BFS guarantee finding the shortest path? Yes, in unweighted graphs where all edges have equal cost. For weighted graphs with edge costs, algorithms like Dijkstra's or A* are needed.
What is the biggest limitation of BFS in production AI? Exponential space growth. Each stored frontier node costs tokens, API calls, or compute cycles, and the Tree of Thoughts paper measured approximately 5× the token cost of single-path methods at b=5. Without depth limits or beam pruning, costs grow multiplicatively with both branching factor and depth.
How is BFS different from vector search? BFS traverses explicit relationships in a graph structure and, given a fixed starting node and neighbor ordering, produces deterministic traversal paths. Vector search finds items by similarity in a high-dimensional embedding space, producing ranked scores without relational context. Many production systems use both in sequence: vector search for entry-point discovery, then graph traversal for context assembly.
