How LeanAgent Uses File Dependency Graphs for Premise Ordering in Proofs

LeanAgent constructs a directed acyclic graph (DAG) of Lean file import relationships to emit premises in topological order, ensuring that any theorem or definition appears only after all of its dependencies have already been recorded.

The lean-dojo/leanagent repository implements a sophisticated dependency resolution system that transforms raw Lean source files into an ordered premise corpus. By leveraging file dependency graphs for premise ordering, LeanAgent guarantees that downstream proof generation components receive premises in a sequence that respects the underlying mathematical dependencies inherent in the Lean codebase.

Building the File Dependency Graph

LeanAgent's dependency analysis begins with traced files and culminates in a verified DAG that represents the import structure of the target repository.

Parsing Traced Files

The process starts in custom_traced_data.py, where each TracedFile object is instantiated from JSON abstract syntax trees generated by Lean's --ast pass. The TracedFile.from_traced_file method deserializes these AST representations, extracting the file's path and content for further analysis.

Resolving Direct Imports

For every traced file, LeanAgent invokes tf.get_direct_dependencies(repo) to identify immediate import relationships. This method yields tuples containing the module name and dependency path. When a dependency is not yet present in the graph, LeanAgent dynamically loads its corresponding *.ast.json file and adds it as a new node.

Constructing the DAG

The _build_dependency_graph function in custom_traced_data.py assembles the complete structure by adding directed edges from importing files to imported files (G.add_edge(tf_path_str, dep_path_str)). Each edge stores the module name for reference. After construction, LeanAgent verifies the graph's integrity with assert nx.is_directed_acyclic_graph(G), ensuring that no circular import relationships exist that would violate topological ordering constraints.

Topological Ordering for Premise Export

Once the dependency graph is established, LeanAgent leverages it to produce a correctly ordered premise corpus for proof generation tasks.

Reversing the Topological Sort

In generate_benchmark_lean4.py, the export_premises function implements the critical ordering logic. Using NetworkX's topological_sort algorithm, LeanAgent generates a sequence where each node appears before its successors. However, since edges point from importers to importees, the raw topological sort would place dependent files first. To ensure that premises appear after their dependencies, LeanAgent reverses this sequence:

for tf_node in reversed(list(nx.topological_sort(G))):
    tf = G.nodes[tf_node]["traced_file"]
    premises = tf.get_premise_definitions()
    # Write to corpus.jsonl

Writing the Premise Corpus

With the reversed topological order established, LeanAgent iterates through files and extracts premises using tf.get_premise_definitions(). Each file's premises are written to corpus.jsonl as JSON objects containing the file path, imports, and premise definitions. Because of the reversed topological sort, any premise that a file imports from another file has already been recorded in the corpus, maintaining referential integrity for downstream proof search components.

Code Implementation Details

The following examples demonstrate how to construct the dependency graph and export ordered premises using LeanAgent's API:

# Building the file dependency graph

from custom_traced_data import _build_dependency_graph, TracedFile
from pathlib import Path

seed_files = [...]  # List[TracedFile] from *.ast.json files

repo_root = Path("/path/to/lean/repo")
repo = LeanGitRepo.from_path(repo_root)

# Construct the DAG

graph = _build_dependency_graph(seed_files, repo_root, repo)
assert nx.is_directed_acyclic_graph(graph)  # Verify no cycles exist

# Exporting premises in dependency order

import networkx as nx
from generate_benchmark_lean4 import export_premises
from pathlib import Path

dst = Path("/output/premise_corpus")
traced_repo = ...  # TracedRepo object containing the graph

# Export with automatic topological ordering

num_premises, num_files = export_premises(traced_repo, dst)

# Internal implementation detail:

# for tf_node in reversed(list(nx.topological_sort(traced_repo.traced_files_graph))):

#     tf = traced_repo.traced_files_graph.nodes[tf_node]["traced_file"]

#     premises = tf.get_premise_definitions()

#     # Write to corpus.jsonl with dependencies already present

Summary

• LeanAgent constructs a directed acyclic graph (DAG) using _build_dependency_graph in custom_traced_data.py to model Lean file import relationships.
• The graph is verified as acyclic using nx.is_directed_acyclic_graph(G) to ensure valid topological ordering is possible.
• Premises are exported in reversed topological order via export_premises in generate_benchmark_lean4.py, ensuring dependencies appear before dependent theorems in corpus.jsonl.
• This ordering guarantees that downstream proof generation components receive premises in a sequence that respects the mathematical dependency structure of the original Lean codebase.

Frequently Asked Questions

How does LeanAgent resolve circular import dependencies?

LeanAgent explicitly checks for cycles after constructing the dependency graph using assert nx.is_directed_acyclic_graph(G) at the end of _build_dependency_graph in custom_traced_data.py. If circular imports are detected, this assertion fails, preventing the system from proceeding with an invalid ordering that would break the premise export process.

Why does LeanAgent reverse the topological sort when exporting premises?

The raw topological sort places importing files before imported files (following the edge direction from importer to importee). However, for premise ordering, LeanAgent needs dependencies to appear first. By reversing the sequence using reversed(list(nx.topological_sort(G))) in generate_benchmark_lean4.py, the system ensures that leaf nodes (base definitions) are written to corpus.jsonl before files that depend on them.

What information is stored in the dependency graph edges?

Each edge in the DAG stores the module name associated with the import relationship. When _build_dependency_graph adds edges via G.add_edge(tf_path_str, dep_path_str), it preserves the module context, allowing LeanAgent to trace not just which files depend on each other, but also through which module paths those dependencies are established.

Which LeanAgent files are responsible for dependency graph construction and premise ordering?

The primary files involved are custom_traced_data.py, which contains the TracedFile class and _build_dependency_graph function for DAG construction, and generate_benchmark_lean4.py, which implements export_premises to perform the reversed topological traversal and write the ordered premise corpus to corpus.jsonl.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}