Heuristic:Diagram of thought Diagram of thought Acyclicity Constraint Enforcement
| Knowledge Sources | |
|---|---|
| Domains | Graph_Processing, Verification |
| Last Updated | 2026-02-14 04:30 GMT |
Overview
Enforce the `src < dst` constraint on all `@edge` records to guarantee DAG acyclicity without requiring a full cycle-detection algorithm.
Description
The DoT typed protocol includes a critical design choice: every `@edge` record must satisfy `src < dst` (the source node ID must be strictly less than the destination node ID). This simple numeric constraint provides a compile-time guarantee of acyclicity without needing runtime cycle detection algorithms. Because node IDs are assigned incrementally during autoregressive generation, any edge pointing "forward" (from lower ID to higher ID) is inherently acyclic. An online validator can check this constraint during generation and reject invalid edges immediately.
Usage
Apply this heuristic when implementing DAG reconstruction from parsed DoT traces (Adjacency_List_Builder implementation) or when building an online validator for DoT output. The constraint should be checked at edge insertion time, not after the full graph is constructed, to catch violations early.
The Insight (Rule of Thumb)
- Action: Validate every `@edge src= dst=<n>` record by checking that `i < n` before adding it to the graph.
- Value: Reject any edge where `src >= dst`. This is a single integer comparison per edge.
- Trade-off: None significant. The check is O(1) per edge and provides a complete acyclicity guarantee. The only limitation is that it prevents "backward" edges, which means the model cannot refine a node that was proposed after the current node (which is semantically correct for DoT's incremental reasoning model).
- Bonus: This also enables topological ordering by node ID (ascending order), eliminating the need for topological sort algorithms.
Reasoning
In a general directed graph, detecting cycles requires O(V+E) algorithms (e.g., DFS-based cycle detection or Kahn's algorithm). The DoT protocol avoids this complexity entirely by constraining edge directions at the protocol level. Since nodes are created in order (id=1, id=2, id=3, ...) during autoregressive generation, requiring `src < dst` means every edge points "forward" in the generation sequence. This is a topological ordering by construction.
This constraint is not just a performance optimization; it reflects the semantic structure of DoT reasoning. A proposition can only build on (use), critique, or refine prior nodes. Allowing backward edges would create temporal paradoxes where a node depends on something that hasn't been proposed yet.
Code evidence from `README.md:L70`:
@edge src=<i> dst=<n> kind={use|critique|refine} (must have i < n)
Code evidence from `README.md:L124`:
This protocol guarantees the graph is acyclic (since @edge sources must have
smaller IDs than destinations) and enables deterministic extraction of the
reasoning structure for analysis. An online validator can enforce these rules
during generation.