taskgraph_ts/tasks/implementation/cost-benefit/dag-propagation.md at main

Files

glm-5.1 7bfcfecc7a feat(cost-benefit/dag-propagation): implement DAG-propagation effective probability computation

Implement computeEffectiveP internal helper and workflowCost public function
that captures the structural reality that upstream failures multiply downstream
damage, per ADR-004 and the Python research model.

- computeEffectiveP: computes pEffective from intrinsic probability + upstream
  propagation using inherited quality factors (parentP + (1-parentP) × qualityRetention)
- workflowCost: processes tasks in topological order, computes per-task EV with
  degraded effective probability, includes pIntrinsic/pEffective split
- Supports independent and dag-propagate modes
- Completed tasks excluded from results but propagate p=1.0 when includeCompleted: false
- Per-edge qualityRetention overrides defaultQualityRetention option
- Throws CircularDependencyError for cyclic graphs via topologicalOrder
- 30+ new tests covering chain compounding, diamond graph, mode comparison,
  completed task semantics, cycle detection, per-edge qualityRetention

2026-04-27 12:52:47 +00:00

3.3 KiB

Raw Permalink Blame History

id, name, status, depends_on, scope, risk, impact, level

name

status

depends_on

scope

risk

impact

level

cost-benefit/dag-propagation

Implement DAG-propagation effective probability computation

completed

cost-benefit/ev-calculation

graph/queries

schema/numeric-methods-and-defaults

moderate

high

phase

implementation

Description

Implement the DAG-propagation cost model in src/analysis/cost-benefit.ts. This is the core algorithmic contribution beyond the Rust CLI — it captures the structural reality that upstream failures multiply downstream damage.

Per cost-benefit.md, the algorithm:

Processes tasks in topological order
For each task with prerequisites, computes pEffective from intrinsic probability + upstream propagation
Upstream propagation: parentP + (1 - parentP) × qualityRetention for each parent
pEffective = intrinsic × product of all inherited quality factors

Acceptance Criteria

computeEffectiveP(taskId, graph, upstreamSuccessProbs, defaultQualityRetention, propagationMode) — internal helper
In dag-propagate mode: for each task in topological order:
- Get intrinsic probability from resolveDefaults(risk).successProbability
- For each prerequisite, compute inherited quality: parentP + (1 - parentP) × qualityRetention
- pEffective = intrinsic × product of all inherited quality factors
- Store task's actual success probability for downstream propagation (use pEffective if this is the task's real probability)
In independent mode: pEffective = pIntrinsic (no propagation)
Completed tasks (status: "completed"): propagate with p = 1.0 when includeCompleted: false
qualityRetention per edge defaults to 0.9, can be overridden per-edge via defaultQualityRetention option or edge attributes
Throws CircularDependencyError if graph is cyclic (needs topo sort)
Unit tests: simple chain (verify compounding effect), diamond graph, independent vs dag-propagate comparison matches Python research model results, completed task exclusion/propagation semantics

References

docs/architecture/cost-benefit.md — DAG-propagation algorithm, qualityRetention semantics
docs/architecture/decisions/004-workflow-cost-dag-propagation.md — ADR-004
docs/architecture/decisions/005-no-depth-escalation-v1.md — no depth escalation in v1

Notes

No depth escalation in v1 per ADR-005 — multiplicative propagation captures depth effects implicitly. Per-edge qualityRetention on edges takes precedence over defaultQualityRetention option. With default EvConfig (no fallbackCost/timeLost), EV = scopeCost × impactWeight regardless of p, so totalEv is similar across modes but pEffective differs.

Summary

Implemented DAG-propagation effective probability computation with computeEffectiveP internal helper and workflowCost public function.

Modified: src/analysis/cost-benefit.ts — added computeEffectiveP and workflowCost functions
Modified: test/cost-benefit.test.ts — added 30+ new tests for DAG propagation
Tests: 63 total in cost-benefit.test.ts, all 476 across test suite passing
Key features: topological ordering, per-edge qualityRetention, independent/dag-propagate modes, completed task exclusion/propagation semantics, CircularDependencyError for cyclic graphs

3.3 KiB Raw Permalink Blame History Unescape Escape