Probabilistic_Graph_Path_Pruning

Validation

It was run inside an isolated container with no network access. This is the exact command and the real output it produced — captured process output, not written by a model.

$ python3 probabilistic_graph_path_pruning_v2.py
[
  {
    "path": "/a/b/c",
    "confidence": 0.8
  },
  {
    "path": "/m/n/o",
    "confidence": 0.5
  }
]

A screenshot of that run.

A clean run proves this does what is shown above, in a CPU-only sandbox. It is a small research demo — not a production tool, and nothing here was published anywhere.

The code

All of it — 84 lines, one file, standard library only.

import collections
import math
import json
class GraphNode:
    def __init__(self, value):
        self.value = value
        self.neighbors = {}
        self.reachability_score = 0
    def add_edge(self, neighbor, confidence):
        self.neighbors[neighbor] = confidence

class ProbabilisticGraph:
    def __init__(self):
        self.nodes = {}
    def add_node(self, value):
        if value not in self.nodes:
            self.nodes[value] = GraphNode(value)
    def add_edge(self, from_value, to_value, confidence):
        self.add_node(from_value)
        self.add_node(to_value)
        self.nodes[from_value].add_edge(self.nodes[to_value], confidence)
    def calculate_reachability_scores(self, max_depth=3):
        for node in self.nodes.values():
            visited = set()
            queue = collections.deque([(node, 1.0)])
            visited.add(node)
            while queue and len(visited) < max_depth:
                current_node, current_confidence = queue.popleft()
                for neighbor, edge_confidence in current_node.neighbors.items():
                    new_confidence = current_confidence * edge_confidence
                    if neighbor not in visited:
                        visited.add(neighbor)
                        queue.append((neighbor, new_confidence))
                node.reachability_score += new_confidence * (0.8 ** len(visited))

    def tree_of_thoughts_search(self, start_value, goal_value, max_paths=5):
        best_paths = []
        stack = [(self.nodes[start_value], [start_value], 1.0)]
        while stack and len(best_paths) < max_paths:
            current_node, path, current_confidence = stack.pop()
            if current_node.value == goal_value:
                best_paths.append((current_confidence, path))
                continue
            # Prune paths with confidence below threshold (relative to best found so far)
            if best_paths:
                prune_limit = 0.1 * max(c[0] for c in best_paths)
                if prune_limit > 1e-9 and current_confidence < prune_limit:
                    continue
            # Calculate entropy penalty for current node's branching
            neighbor_confs = list(current_node.neighbors.values())
            if neighbor_confs and len(neighbor_confs) > 1:
                total_conf = sum(neighbor_confs)
                probs = [conf/total_conf for conf in neighbor_confs]
                entropy = -sum(p * math.log2(p) for p in probs if p > 0)
                n = len(neighbor_confs)
                max_entropy = math.log2(n)
                # Normalized entropy ratio: 0 = certainty, 1 = max uncertainty
                ent_norm = entropy / max_entropy
                # Soft penalty: scales confidence down but never below 0.2
                entropy_penalty = 1.0 - 0.8 * ent_norm
            else:
                entropy_penalty = 1.0
            # Sort neighbors by reachability score descending
            sorted_neighbors = sorted(
                current_node.neighbors.items(),
                key=lambda x: x[1] * self.nodes[x[0].value].reachability_score, reverse=True
            )
            for neighbor, confidence in sorted_neighbors:
                new_conf = current_confidence * confidence * entropy_penalty
                stack.append((neighbor, path + [neighbor.value], new_conf))
        return sorted(best_paths, reverse=True)

if __name__ == "__main__":
    graph = ProbabilisticGraph()
    graph.add_edge('A', 'B', 0.8)
    graph.add_edge('A', 'C', 0.5)
    graph.add_edge('B', 'D', 0.9)
    graph.add_edge('C', 'D', 0.7)
    graph.add_edge('D', 'Goal', 1.0)
    graph.calculate_reachability_scores(max_depth=3)
    best_paths = graph.tree_of_thoughts_search('A', 'Goal', max_paths=3)
    print("\nBest paths from A to Goal (confidence, path):")
    for confidence, path in best_paths:
        print(f'Confidence: {confidence:.2f}, Path: {".".join(path)}')