Skip to content

🪢 Open source agent evals & observability: Trace, evaluate, and improve LLM applications with one open platform.

9.0 KB
Raw Blame
import { ObservationType } from "@langfuse/shared";
import {
  type AgentGraphDataResponse,
  LANGFUSE_START_NODE_NAME,
  LANGFUSE_END_NODE_NAME,
} from "./types";

function takeNextStepGroup(
  observations: AgentGraphDataResponse[],
  timestampCache: Map<string, { start: number; end: number }>,
): {
  cleanedGroup: AgentGraphDataResponse[];
  unprocessed: AgentGraphDataResponse[];
} {
  // create observation group and put the beginning observation in it
  const currentGroup = [observations[0]];
  const remainingObs = observations.slice(1);

  // Track max end time for early termination optimization
  let maxGroupEndTime = timestampCache.get(observations[0].id)!.end;

  // loop through all remaining observations that are not added to any group yet
  for (const obs of remainingObs) {
    const obsStart = timestampCache.get(obs.id)!.start;

    // Optimization: early break if current observation starts after all current group members finish
    if (obsStart >= maxGroupEndTime) {
      break;
    }

    // if observation starts before any observations in current group finished, add it to the current group
    const startsBeforeAnyFinishes = currentGroup.some((groupObs) => {
      const groupEnd = timestampCache.get(groupObs.id)!.end;
      return obsStart < groupEnd;
    });

    if (startsBeforeAnyFinishes) {
      currentGroup.push(obs);
      // Update max end time for this group
      const obsEnd = timestampCache.get(obs.id)!.end;
      if (obsEnd > maxGroupEndTime) {
        maxGroupEndTime = obsEnd;
      }
    }
  }

  const cleanedGroup: AgentGraphDataResponse[] = [];
  // Track unprocessed incrementally during cleanup phase
  const processedIds = new Set<string>();

  // build final current group. check if observation doesn't start after any finishes, only then add it
  currentGroup.forEach((obs) => {
    const obsStart = timestampCache.get(obs.id)!.start;

    const startsAfterAnyOtherFinishes = currentGroup.some((otherObs) => {
      if (otherObs === obs) return false;

      const otherEnd = timestampCache.get(otherObs.id)!.end;
      return obsStart > otherEnd; // handle simultaneous events gracefully
    });

    if (!startsAfterAnyOtherFinishes) {
      cleanedGroup.push(obs);
      processedIds.add(obs.id);
    }
  });

  // Inverted or otherwise invalid time ranges can cause cleanup to remove every
  // observation. Keep the original group so grouping always makes progress.
  if (cleanedGroup.length === 0) {
    cleanedGroup.push(...currentGroup);
    currentGroup.forEach((o) => processedIds.add(o.id));
  }

  return {
    cleanedGroup,
    unprocessed: observations.filter((obs) => !processedIds.has(obs.id)),
  };
}

function buildStepGroups(
  observations: AgentGraphDataResponse[],
  timestampCache: Map<string, { start: number; end: number }>,
): AgentGraphDataResponse[][] {
  const stepGroups: AgentGraphDataResponse[][] = [];
  let remaining = observations;

  // Iterative so a long sequential chain (one group per observation) cannot
  // overflow the call stack.
  while (remaining.length > 0) {
    const remainingCount = remaining.length;
    const { cleanedGroup, unprocessed } = takeNextStepGroup(
      remaining,
      timestampCache,
    );

    if (cleanedGroup.length === 0 || unprocessed.length >= remainingCount) {
      stepGroups.push([remaining[0]]);
      remaining = remaining.slice(1);
      continue;
    }

    stepGroups.push(cleanedGroup);
    remaining = unprocessed;
  }

  return stepGroups;
}

function assignGlobalTimingSteps(
  data: AgentGraphDataResponse[],
): AgentGraphDataResponse[] {
  const dataCopy: AgentGraphDataResponse[] = [];
  const timestampCache = new Map<string, { start: number; end: number }>();
  for (const obs of data) {
    const obsCopy = { ...obs };
    dataCopy.push(obsCopy);
    timestampCache.set(obs.id, {
      start: new Date(obs.startTime).getTime(),
      end: obs.endTime
        ? new Date(obs.endTime).getTime()
        : new Date(obs.startTime).getTime(),
    });
  }

  // sort observations by start time
  const sortedObs = [...dataCopy].sort(
    (a, b) => timestampCache.get(a.id)!.start - timestampCache.get(b.id)!.start,
  );

  const stepGroups = buildStepGroups(sortedObs, timestampCache);

  // assign step numbers and flatten
  let result: AgentGraphDataResponse[] = [];
  stepGroups.forEach((group, stepIndex) => {
    group.forEach((obs) => {
      obs.step = stepIndex + 1;
      obs.node = obs.name;
      result.push(obs);
    });
  });

  // apply span parent-child step constraint: any child must be at least parent_step + 1
  // any step groups down the line will be pushed down by the same amount
  let constraintViolations = true;
  let iterationCount = 0;
  const MAX_ITERATIONS = 1500;

  while (constraintViolations) {
    iterationCount++;

    if (iterationCount > MAX_ITERATIONS) {
      console.debug("Aborting graph processing due to excessive iterations.");
      break;
    }

    constraintViolations = false;
    // Track step adjustments to apply during result building
    const adjustments = new Map<string, number>();
    const obsMap = new Map(result.map((o) => [o.id, o]));

    // helper to get all ancestors of an observation
    const getAncestors = (obsId: string): Set<string> => {
      const ancestors = new Set<string>();
      let current = obsMap.get(obsId);
      while (current?.parentObservationId) {
        const parentId = current.parentObservationId;
        // Cycle guard: parent pointers are acyclic by DB schema, but a malformed
        // chain (parent already seen) would otherwise loop this walk forever.
        if (ancestors.has(parentId)) break;
        ancestors.add(parentId);
        current = obsMap.get(parentId);
      }
      return ancestors;
    };

    // identify spans which must be pushed (violations) and calculate adjustments
    for (const obs of result) {
      if (!obs.parentObservationId || obs.step === null) continue;

      const parent = obsMap.get(obs.parentObservationId);
      if (!parent || parent.step === null) continue;

      const requiredMinStep = parent.step + 1;
      if (obs.step < requiredMinStep) {
        constraintViolations = true;
        const ancestors = getAncestors(obs.id);

        // adjust the violating child and push all observations at future steps forward (except ancestors)
        for (const target of result) {
          if (target.step === null) continue;

          if (target.id === obs.id) {
            // child adjustment
            adjustments.set(
              target.id,
              (adjustments.get(target.id) || 0) + (requiredMinStep - obs.step),
            );
          } else if (
            target.step >= requiredMinStep &&
            !ancestors.has(target.id)
          ) {
            // Push forward observations at future steps except for ancestors
            adjustments.set(target.id, (adjustments.get(target.id) || 0) + 1);
          }
        }
      }
    }

    result = result.map((obs) => ({
      ...obs,
      step:
        obs.step !== null
          ? obs.step + (adjustments.get(obs.id) || 0)
          : obs.step,
    }));
  } // end loop to check if parent-child constraints require step adjustments

  return result;
}

function addLangfuseSystemNodes(
  data: AgentGraphDataResponse[],
): AgentGraphDataResponse[] {
  const systemNodes: AgentGraphDataResponse[] = [];

  // Find the top-level parent for system node mapping
  const topLevelObs = data.find((obs) => !obs.parentObservationId);

  // Use deterministic timestamp to avoid infinite re-renders
  const systemTimestamp = "2024-01-01T00:00:00.000Z";

  // Add __start_lf__ node at step 0
  systemNodes.push({
    id: LANGFUSE_START_NODE_NAME,
    name: LANGFUSE_START_NODE_NAME,
    node: LANGFUSE_START_NODE_NAME,
    step: 0,
    parentObservationId: topLevelObs?.parentObservationId || null,
    startTime: systemTimestamp,
    endTime: systemTimestamp,
    observationType: "LANGGRAPH_SYSTEM",
  });

  // Add __end_lf__ node at max step + 1
  const maxStep = Math.max(...data.map((obs) => obs.step || 0));
  systemNodes.push({
    id: LANGFUSE_END_NODE_NAME,
    name: LANGFUSE_END_NODE_NAME,
    node: LANGFUSE_END_NODE_NAME,
    step: maxStep + 1,
    parentObservationId: topLevelObs?.parentObservationId || null,
    startTime: systemTimestamp,
    endTime: systemTimestamp,
    observationType: "LANGGRAPH_SYSTEM",
  });

  return [...data, ...systemNodes];
}

export function buildStepData(
  agentGraphData: AgentGraphDataResponse[],
): AgentGraphDataResponse[] {
  // for now, we don't want to show SPAN/EVENTs in our agent graphs
  // TODO: move this filter to a separate function
  const filteredData = agentGraphData.filter(
    (item) =>
      // Just not show events for now
      // item.observationType !== ObservationType.SPAN &&
      // item.observationType !== ObservationType.GENERATION &&
      item.observationType !== ObservationType.EVENT,
  );

  // Assign step numbers based on global timing analysis
  const dataWithSteps = assignGlobalTimingSteps(filteredData);

  // Add Langfuse system nodes to make it consistent with LangGraph path
  const dataWithSystemNodes = addLangfuseSystemNodes(dataWithSteps);

  return dataWithSystemNodes;
}