langchain-ai/langgraph
1
0
Fork 0
mirror of https://github.com/langchain-ai/langgraph.git synced 2026-07-15 12:35:43 -04:00
Code Issues 314 Packages Projects Releases 17 Wiki Activity

The breadth-first progression of the graph creates a lot of bugs and unintended consequences in langgraph #931

New Issue
Closed
opened 2026-02-20 17:42:25 -05:00 by yindo · 1 comment
yindo commented 2026-02-20 17:42:25 -05:00
Owner
Copy Link
Copy Source

Originally created by @spandan-sharma on GitHub (Aug 22, 2025).

Checked other resources

  • This is a bug, not a usage question. For questions, please use the LangChain Forum (https://forum.langchain.com/).
  • I added a clear and detailed title that summarizes the issue.
  • I read what a minimal reproducible example is (https://stackoverflow.com/help/minimal-reproducible-example).
  • I included a self-contained, minimal example that demonstrates the issue INCLUDING all the relevant imports. The code run AS IS to reproduce the issue.

Example Code

#!/usr/bin/env python3

"""
Please check the diagram and description for explanations.
"""

import asyncio
from typing import Annotated, TypedDict

from langchain_core.messages import BaseMessage
from langgraph.graph import END, START, StateGraph, add_messages
from langgraph.graph.state import CompiledStateGraph


class State(TypedDict):
    messages: Annotated[list[str | BaseMessage], add_messages]


async def node1(state: State) -> State:
    print("Node1:", "\n".join(m.content for m in state.get("messages")) or "<No incoming state>")
    print("-------------------")
    return State(messages=["from n1"])


async def node3(state: State) -> State:
    print("Node3:", "\n".join(m.content for m in state.get("messages")))
    print("-------------------")
    return State(messages=["from n3"])


async def node4(state: State) -> State:
    print("Node4:", "\n".join(m.content for m in state.get("messages")))
    print("-------------------")
    return State(messages=["from n4"])


async def node5(state: State) -> State:
    print("Node5:", "\n".join(m.content for m in state.get("messages")))
    print("-------------------")
    return State(messages=["from n5"])


async def node6(state: State) -> State:
    print("Node6:", "\n".join(m.content for m in state.get("messages")))
    print("-------------------")
    return State(messages=["from n6"])


async def node7(state: State) -> State:
    print("Node7:", "\n".join(m.content for m in state.get("messages")))
    print("-------------------")
    return State(messages=["from n7"])


async def node8(state: State) -> State:
    print("Node8:", "\n".join(m.content for m in state.get("messages")))
    print("-------------------")
    return State(messages=["from n8"])


async def node9(state: State) -> State:
    print("Node9:", "\n".join(m.content for m in state.get("messages")))
    print("-------------------")
    return State(messages=["from n9"])


async def node10(state: State) -> State:
    print("Node10:", "\n".join(m.content for m in state.get("messages")))
    print("-------------------")
    return State(messages=["from n10"])


async def main():
    graph = StateGraph(State)
    graph.add_node(node1)
    graph.add_node(node3)
    graph.add_node(node4)
    graph.add_node(node5)
    graph.add_node(node6)
    graph.add_node(node7)
    graph.add_node(node8)
    graph.add_node(node9)
    graph.add_node(node10)

    graph.add_edge(START, "node1")
    graph.add_edge("node1", "node3")
    graph.add_edge("node1", "node4")
    graph.add_edge("node3", "node5")
    graph.add_edge("node3", "node6")
    graph.add_edge("node4", "node7")
    graph.add_edge("node4", "node8")
    graph.add_edge("node6", "node9")
    graph.add_edge("node7", "node9")
    graph.add_edge("node5", "node10")
    graph.add_edge("node8", "node10")
    graph.add_edge("node9", "node10")
    ###############################################################
    graph.add_edge("node10", END)

    workflow: CompiledStateGraph = graph.compile(name="app2")

    _result = await workflow.ainvoke(input=State())


if __name__ == "__main__":
    asyncio.run(main())

Error Message and Stack Trace (if applicable)

Node1: <No incoming state>
-------------------
Node3: from n1
-------------------
Node4: from n1
-------------------
Node5: from n1
from n3
from n4
-------------------
Node6: from n1
from n3
from n4
-------------------
Node7: from n1
from n3
from n4
-------------------
Node8: from n1
from n3
from n4
-------------------
Node10: from n1
from n3
from n4
from n5
from n6
from n7
from n8
-------------------
Node9: from n1
from n3
from n4
from n5
from n6
from n7
from n8
-------------------
Node10: from n1
from n3
from n4
from n5
from n6
from n7
from n8
from n10
from n9
-------------------

Description

Langgraph's StateGraph seems to be doing a breadth-first traversal for its progression. Here's the graph for the code above:

            __start__
                |
              node1
                |
       -----------------
      |                 |
    node3             node4
      |                 |
  ---------        ----------
 |          |     |          |
node5     node6  node7     node8
  |         |     |          |
  |          -----           |
  |            |             |
  |          node9           |
  |            |             |
   --------------------------
               |
             node10
               |
            __end__
  1. It progresses to the "next level" only if current level is completely solved even if some of the next level nodes have no dependency on it. Eg. if node4 takes X units of time to resolve and node6 Y units then an orchestration engine could have executed both node4 and node6 in parallel and their combined resolution would take max(X, Y) units of time. However if we do a breadth first traversal at every "super step" blindly then we lose the optimistic execution based on a given lineage and although node6 has no dependency on node4 or any of its data it doesn't get executed until node4 completes execution. The overall execution then takes X + Y units of time. This will be repeated for all such occurrences and we totally lose the benefits of lineage based parallelism resulting in an unnecessarily slow workflow.
  2. This also results in bugs - again due to no lineage tracking. All the breadth-first children are collected before execution and they are all then executed. So [node3, node4] are collected and executed. Then all their children [node5, node6, node7, node8] are collected and executed. However the next level is skewed - children of [node5 ,6, 7, 8] are [node9, node10]. But because of lack of lineage tracking, the orchestration doesn't realise that node10 has a hard dependency on node9. It simply executes all nodes from this level and thus 10 and 9 are both executed in exactly that order due to left-right BFS associativity. The execution of 10 is bogus since it never received its promised data (or any other side effect) from 9.
  3. Now we again do a level scoop and find 9 has a child 10 and re-excute 10 agian. This is quite bad as it breaks the ability to reason about node executions. You can see from the output above that 10 is executed twice - once with and once without data/side-effects from 9, breaking the orchestration contract.

These are some of the IMO adverse consequences. As you can imagine depending of the graph structure, it'll have many more.

System Info

The following is from pip freeze:

langchain==0.3.27
langchain-community==0.3.27
langchain-core==0.3.74
langchain-openai==0.3.31
langchain-text-splitters==0.3.9
langgraph==0.6.6
langgraph-checkpoint==2.1.1
langgraph-checkpoint-sqlite==2.0.11
langgraph-prebuilt==0.6.4
langgraph-sdk==0.2.3
langsmith==0.4.15

Python:

$ python --version
Python 3.13.5

OS: MacOS

Originally created by @spandan-sharma on GitHub (Aug 22, 2025). ### Checked other resources - [x] This is a bug, not a usage question. For questions, please use the LangChain Forum (https://forum.langchain.com/). - [x] I added a clear and detailed title that summarizes the issue. - [x] I read what a minimal reproducible example is (https://stackoverflow.com/help/minimal-reproducible-example). - [x] I included a self-contained, minimal example that demonstrates the issue INCLUDING all the relevant imports. The code run AS IS to reproduce the issue. ### Example Code ```python #!/usr/bin/env python3 """ Please check the diagram and description for explanations. """ import asyncio from typing import Annotated, TypedDict from langchain_core.messages import BaseMessage from langgraph.graph import END, START, StateGraph, add_messages from langgraph.graph.state import CompiledStateGraph class State(TypedDict): messages: Annotated[list[str | BaseMessage], add_messages] async def node1(state: State) -> State: print("Node1:", "\n".join(m.content for m in state.get("messages")) or "<No incoming state>") print("-------------------") return State(messages=["from n1"]) async def node3(state: State) -> State: print("Node3:", "\n".join(m.content for m in state.get("messages"))) print("-------------------") return State(messages=["from n3"]) async def node4(state: State) -> State: print("Node4:", "\n".join(m.content for m in state.get("messages"))) print("-------------------") return State(messages=["from n4"]) async def node5(state: State) -> State: print("Node5:", "\n".join(m.content for m in state.get("messages"))) print("-------------------") return State(messages=["from n5"]) async def node6(state: State) -> State: print("Node6:", "\n".join(m.content for m in state.get("messages"))) print("-------------------") return State(messages=["from n6"]) async def node7(state: State) -> State: print("Node7:", "\n".join(m.content for m in state.get("messages"))) print("-------------------") return State(messages=["from n7"]) async def node8(state: State) -> State: print("Node8:", "\n".join(m.content for m in state.get("messages"))) print("-------------------") return State(messages=["from n8"]) async def node9(state: State) -> State: print("Node9:", "\n".join(m.content for m in state.get("messages"))) print("-------------------") return State(messages=["from n9"]) async def node10(state: State) -> State: print("Node10:", "\n".join(m.content for m in state.get("messages"))) print("-------------------") return State(messages=["from n10"]) async def main(): graph = StateGraph(State) graph.add_node(node1) graph.add_node(node3) graph.add_node(node4) graph.add_node(node5) graph.add_node(node6) graph.add_node(node7) graph.add_node(node8) graph.add_node(node9) graph.add_node(node10) graph.add_edge(START, "node1") graph.add_edge("node1", "node3") graph.add_edge("node1", "node4") graph.add_edge("node3", "node5") graph.add_edge("node3", "node6") graph.add_edge("node4", "node7") graph.add_edge("node4", "node8") graph.add_edge("node6", "node9") graph.add_edge("node7", "node9") graph.add_edge("node5", "node10") graph.add_edge("node8", "node10") graph.add_edge("node9", "node10") ############################################################### graph.add_edge("node10", END) workflow: CompiledStateGraph = graph.compile(name="app2") _result = await workflow.ainvoke(input=State()) if __name__ == "__main__": asyncio.run(main()) ``` ### Error Message and Stack Trace (if applicable) ```shell Node1: <No incoming state> ------------------- Node3: from n1 ------------------- Node4: from n1 ------------------- Node5: from n1 from n3 from n4 ------------------- Node6: from n1 from n3 from n4 ------------------- Node7: from n1 from n3 from n4 ------------------- Node8: from n1 from n3 from n4 ------------------- Node10: from n1 from n3 from n4 from n5 from n6 from n7 from n8 ------------------- Node9: from n1 from n3 from n4 from n5 from n6 from n7 from n8 ------------------- Node10: from n1 from n3 from n4 from n5 from n6 from n7 from n8 from n10 from n9 ------------------- ``` ### Description Langgraph's `StateGraph` seems to be doing a breadth-first traversal for its progression. Here's the graph for the code above: ``` __start__ | node1 | ----------------- | | node3 node4 | | --------- ---------- | | | | node5 node6 node7 node8 | | | | | ----- | | | | | node9 | | | | -------------------------- | node10 | __end__ ``` 1. It progresses to the "next level" only if current level is completely solved even if some of the next level nodes have no dependency on it. Eg. if `node4` takes `X` units of time to resolve and `node6` `Y` units then an orchestration engine could have executed both `node4` and `node6` in parallel and their combined resolution would take `max(X, Y)` units of time. However if we do a breadth first traversal at every "super step" blindly then we lose the optimistic execution based on a given lineage and although `node6` has no dependency on `node4` or any of its data it doesn't get executed until `node4` completes execution. The overall execution then takes `X + Y` units of time. This will be repeated for all such occurrences and we totally lose the benefits of lineage based parallelism resulting in an unnecessarily slow workflow. 2. This also results in bugs - again due to no lineage tracking. All the breadth-first children are collected before execution and they are all then executed. So `[node3, node4]` are collected and executed. Then all their children `[node5, node6, node7, node8]` are collected and executed. However the next level is skewed - children of `[node5 ,6, 7, 8]` are `[node9, node10]`. But because of lack of lineage tracking, the orchestration doesn't realise that `node10` has a hard dependency on `node9`. It simply executes all nodes from this level and thus `10` and `9` are both executed in exactly that order due to left-right BFS associativity. The execution of `10` is bogus since it never received its promised data (or any other side effect) from `9`. 3. Now we again do a level scoop and find `9` has a child `10` and _re-excute_ `10` _agian_. This is quite bad as it breaks the ability to reason about node executions. You can see from the output above that `10` is executed twice - once with and once without data/side-effects from `9`, breaking the orchestration contract. These are some of the IMO adverse consequences. As you can imagine depending of the graph structure, it'll have many more. ### System Info The following is from `pip freeze`: ``` langchain==0.3.27 langchain-community==0.3.27 langchain-core==0.3.74 langchain-openai==0.3.31 langchain-text-splitters==0.3.9 langgraph==0.6.6 langgraph-checkpoint==2.1.1 langgraph-checkpoint-sqlite==2.0.11 langgraph-prebuilt==0.6.4 langgraph-sdk==0.2.3 langsmith==0.4.15 ``` Python: ``` $ python --version Python 3.13.5 ``` OS: `MacOS`
yindo added the bugpending labels 2026-02-20 17:42:25 -05:00
yindo closed this issue 2026-02-20 17:42:25 -05:00
yindo commented 2026-02-20 17:42:25 -05:00
Author
Owner
Copy Link
Copy Source

@spandan-sharma commented on GitHub (Aug 25, 2025):

I'm closing this issue (reluctantly) because I found out that there's another attribute, defer=True which can be set on nodes to "defer" their execution for later.

Firstly one needs to understand how this defer=True works: From what I observed, on any node it's set, the node when it's considered for execution will get pushed to a (hypothetical) deferred queue. When the graph can no longer make progress it'll then dequeue all nodes from this queue and execute them and then the normal flow begins again, until another deferred node is encountered or the graph reaches the end.

In this example it's trivial to work out - we need defer=True for node10 so that it allows for node9 to finish its execution and then since there are no pending nodes (ie graph cannot make progress anymore) node10 is dequeued and executed.

However:

  1. This is nightmarish and error prone to work out in even a slightly more complex graph.
  2. I find this behaviour to be a bug where in defer=True kinda "hack" is needed to fix it - the graph traversal is not respecting dependency ordering crafted by the user. What even is the point of creating a graph if descendants can be executed without their ancestors having produced their output(s) or side-effect(s) which the descendants might rely on?
  3. More importantly, this (defer=True) doesn't solve anything because I believe it's fundamentally broken - I've raised another issue explaining that: https://github.com/langchain-ai/langgraph/issues/6005
@spandan-sharma commented on GitHub (Aug 25, 2025): I'm closing this issue (reluctantly) because I found out that there's another attribute, `defer=True` which can be set on nodes to "defer" their execution for later. Firstly one needs to understand how this `defer=True` works: From what I observed, on any node it's set, the node when it's considered for execution will get pushed to a (hypothetical) `deferred` queue. When the graph can no longer make progress it'll then dequeue all nodes from this queue and execute them and then the normal flow begins again, until another deferred node is encountered or the graph reaches the end. In this example it's trivial to work out - we need `defer=True` for `node10` so that it allows for `node9` to finish its execution and then since there are no pending nodes (ie graph cannot make progress anymore) `node10` is dequeued and executed. However: 1. This is nightmarish and error prone to work out in even a slightly more complex graph. 2. I find this behaviour to be a bug where in `defer=True` kinda "hack" is needed to fix it - the graph traversal is not respecting dependency ordering crafted by the user. What even is the point of creating a graph if descendants can be executed without their ancestors having produced their output(s) or side-effect(s) which the descendants might rely on? 3. More importantly, this (`defer=True`) doesn't solve anything because I believe it's fundamentally broken - I've raised another issue explaining that: https://github.com/langchain-ai/langgraph/issues/6005
Sign in to join this conversation.
No Branch/Tag Specified
Branches Tags
Labels
Clear labels
agents
awaiting author revision
bug
change
chat models
checkpointer
ci
code quality
code quality
dependencies
documentation
drawing
duplicate
enhancement
good first issue
help wanted
invalid
maintainer
meta
missing information
not maintained by langchain
open-swe-auto
open-swe-max
open-swe-max-auto
pending
performance
pull-request
Mirrored from GitHub Pull Request
 question
requires design
sdk
server
stale
studio
tests
type checking
usage question
v0.5
v1.1
No Label bug pending
Milestone
No items
No Milestone
Projects
Clear projects
No project
Assignees
Clear assignees
yindo
No Assignees
1 Participants
Notifications
Due Date
No due date set.
Dependencies

No dependencies set.

Reference: langchain-ai/langgraph#931
Delete Branch "%!s()"

Deleting a branch is permanent. Although the deleted branch may continue to exist for a short time before it actually gets removed, it CANNOT be undone in most cases. Continue?