Task graphs for AI coding agents with Beads

A task graph is all tracked tasks and the dependencies between them. AR Labs keeps its task graph for AI coding agents (AI agents that write code, such as Claude Code or Codex) in Beads, Steve Yegge's open-source issue tracker for coding agents. Each tracked task, called a bead, sits in a tree of parents and children and carries explicit blocking edges to the beads it depends on. Agents take work from the set of beads whose blockers have all closed, so the graph itself says what can start next, and the coding pipeline keeps its entire state on the beads themselves. The practice suits anyone whose task list has stopped saying what must finish before what.

The problem it prevents

Most task tools treat hierarchy as categorisation (epic, story, task as size buckets) and dependency as an optional extra. The structure you see then says nothing about what must finish before what. Tasks pile up with no visible link to their goals, everything looks equally urgent, and the tool slowly becomes a graveyard of orphaned issues. Early on, our own graph reached several hundred beads and edges with no view of which mattered.

We think hierarchy should encode the order in which work resolves. A parent cannot close until its children have. Leaves are where attention goes, and resolution flows from the leaves toward the root. Ordered that way, the tree is the execution plan: a topological sort of a directed acyclic graph.

How it works

In the example, closing the tracer slice has unblocked two beads: one is now in progress and the other is ready. A fourth waits on the ready one, and a bug found along the way is linked to the work that found it. Beads stores only open, in progress and closed; whether a bead is ready or blocked is worked out from its edges each time someone asks.

Beads distinguishes edge types, and we use each for one job:

bd create "Export all sessions" --parent app-42 -t task -p 1
bd dep add app-42.2 app-42.1     # app-42.2 is blocked by app-42.1
bd ready                         # open beads with no open blockers

Rules that keep the graph trustworthy

A graph is only useful for dispatching work if its structure can be believed. We keep these rules:

• One structural parent per bead. discovered-from records where work came from and never replaces parentage.
• File found work under the nearest open workstream, not under a leaf that is about to close.
• Search before creating. Reuse, extend or add a child to matching work rather than creating a duplicate.
• Use blocking edges for order. When provenance and ordering compete for the same pair of beads, keep the blocking edge and record provenance in notes.
• Do not redefine the tracker's lifecycle. Status stays open, in_progress, closed. Pipeline position (spec, implement, review) lives in namespaced metadata owned by the pipeline. We once used custom statuses for pipeline stages, and retired them so that the status column means only what Beads says it means. A hook now refuses the retired status names.
• Never force-close around open children. A forced close leaves a readable graph with a closed parent above unresolved work. The same hook refuses it, along with cascading deletes.
• Write beads for a human reader. Titles are four to eight plain words naming the problem or outcome. Descriptions open with one sentence a stranger can follow. Execution state goes in status and the append-only notes, not in the description, where it would be stale the next day.

What our research found

Before building tools that turn the graph into an order of work, we researched scheduling theory and how teams running parallel agents dispatch work. Four findings shape the practice:

1. Dispatch from a ready queue, not in waves. List scheduling keeps the set of beads whose blockers have closed, ranks them by the longest chain of work still waiting on each, and gives the top one to whichever agent is free. R. L. Graham's bound guarantees that any such list schedule finishes within (2 − 1/m) times the best possible time on m workers. Making wave N wait for all of wave N−1 loses that guarantee, because one slow item idles the pool.
2. A missing edge means "not assessed", not "independent". Schedule health checks such as the US Defense Contract Management Agency's 14-point assessment flag tasks with no logic links. Our display rules treat a bead with no edges as an error, never as ready.
3. A file conflict is a lock, not a dependency. Two tasks that touch the same file cannot run together, but either may go first. Writing that as a blocking edge imposes an order nobody needs. The alternative is a declared file scope per task, enforced when work is dispatched.
4. Models infer dependencies worse than they infer tasks. When an agent proposes a plan, review effort belongs on its edges.

A health check that cannot lie

Tracker health is checked by running a real query and inspecting its exit status, not by counting lines of output. An earlier check discarded errors and counted display lines, so a broken installation looked like an empty, healthy one. During a database migration, every session opened reporting zero tasks against a fully populated store. The fix was to treat a failed command as a failure.

Where it came from

Beads is Steve Yegge's project. The vertical-slice, blocking-edge style of breaking work down follows Matt Pocock's workflow, in which each slice is an independently grabbable issue that states what blocks it. The scheduling result is R. L. Graham's.