autosearch:graph-search-plan

Graph Search Plan — DAG Over Research Sub-Questions

Most research plans are flat (list) or shallow tree (decompose-task). When sub-questions have dependencies ("to answer Q3, first need answers from Q1 and Q2"), a DAG captures the structure more accurately and enables parallelism.

Node

node:
  id: str                           # "root", "q1", "q1a", ...
  question: str
  rationale: str
  depends_on: list[str]             # node ids whose answers are required first
  status: "pending" | "running" | "done" | "failed" | "skipped"
  assigned_subtask_id: str | null   # link to a delegate-subtask when executed
  answer_summary: str | null        # populated when status == "done"
  answer_evidence: list[dict] | null

Graph

graph:
  nodes: dict[str, Node]
  edges: list[tuple[from_id, to_id]]  # redundant but convenient — derivable from depends_on
  root_id: "root"
  status: "planning" | "executing" | "finalizing" | "complete" | "failed"
  adjacency: dict[str, list[str]]     # node_id → successor ids (for bfs)

Invariants

1. Acyclic: runtime AI must validate no cycles when generating the plan. Cycle → reject plan, re-decompose.
2. Connected: every node is reachable from root_id (directly or transitively via predecessors).
3. Dependencies exist: every depends_on id appears in nodes.

Execution Policy

At each tick:

ready_nodes = [n for n in graph.nodes.values()
               if n.status == "pending"
               and all(graph.nodes[d].status == "done" for d in n.depends_on)]

# Limit parallelism
take = ready_nodes[:max_parallel_nodes]  # e.g. 4
for node in take:
    subtask_id = delegate_subtask(node.question, ...)
    node.status = "running"
    node.assigned_subtask_id = subtask_id

On subtask completion, set node.status = "done" and store answer_summary + answer_evidence. Re-run ready-node detection; if new nodes become ready, dispatch them.

Graph Generation (Planner)

Initial plan (Best-tier LLM):