Large Language Models (LLMs) have mastered the art of writing individual functions, but they often fail at the "boss level" of software engineering: generating entire, coherent repositories. When an agent attempts to build a multi-file project in a single block or a random sequence, it frequently hallucinates non-existent APIs, creates circular imports, or produces redundant implementations.
To solve this, a growing body of research focuses on dependency-guided synthesis. The core intuition is that software is not a linear sequence of text, but a Directed Acyclic Graph (DAG) of functional requirements. By extracting this graph and traversing it in a specific order—usually from the "leaves" (utilities) to the "root" (main logic)—automated systems can ensure that every line of code is built upon a verified foundation.
The Repository as a Directed Graph
Traditional code generation treats a prompt as a request for a flat file. However, as Daoguang Zan and colleagues argue in their work on CODES, repository-level generation requires a multi-layer "sketch." This involves mapping directory hierarchies and cross-file imports before writing a single line of logic.
This mapping creates a Repository Planning Graph (RPG), a concept formalized by Jane Luo and Jie Wu in the ZeroRepo framework. The RPG replaces ambiguous natural language plans with a formal blueprint of data flows and dependencies. By treating the repository as a graph, the system can identify which components are prerequisites for others, preventing the common issue where a model attempts to call a function that hasn't been defined yet.
Topological Ordering and Bottom-Up Construction
Once a dependency graph is established, the most effective way to process it is through topological sorting. This algorithm arranges the nodes such that for every directed edge from component A to component B, A appears before B in the sequence.
In the context of code generation, this translates to a bottom-up strategy:
- Leaf Nodes: Implement basic data structures, constants, and utility functions that have no internal dependencies.
- Intermediate Nodes: Implement modules that rely only on the already-completed leaf nodes.
- Root Nodes: Implement the high-level orchestration logic and main entry points.
Shijie Wang and the creators of CodeFlowBench demonstrate that this iterative, multi-turn process is significantly more reliable than monolithic generation. Similarly, Jinheon Baek uses this "dependency-aware sequential synthesis" in PaperCoder to implement machine learning papers, ensuring that complex model architectures are aware of the specific interfaces provided by their data-loading prerequisites.
Why It Works: Context Propagation and Verification
The power of topological synthesis lies in how it manages the LLM's context window and error propagation.
- Contextual Grounding: When a model generates a high-level function, the bottom-up approach ensures that the actual implementations of its dependencies are already in the context. Rui Li and Qi Liu leverage this in Query4Code by propagating summaries of leaf functions upward, allowing the model to understand hierarchical structures through incremental aggregation.
- Incremental Verification: By following a graph, systems can apply Test-Driven Development (TDD) at each node. Jane Luo notes that each component can be validated with unit tests before the system proceeds to its dependents. This prevents "hallucinated dependencies" from polluting the rest of the codebase.
- Stability in Refinement: In project-level optimization, Xiaoxue Ren and Yutong Cheng show that stabilizing foundational code before their callers prevents "whack-a-mole" bugs, where fixing one function invalidates the logic of everything that calls it.
Applications in Translation and Training
This graph-based intuition extends beyond generation into code migration and model pretraining.
In C-to-Rust translation, tools like SACTOR and Syzygy decompose source code into a dependency graph of types and functions. By translating from the leaves upward, they ensure that Rust's strict ownership and lifetime requirements are satisfied incrementally. Manish Shetty highlights that this prevents error cascades, as low-level modules are fully verified before they are utilized by higher-level components.
Even the way models learn code is being reshaped by this idea. Matt Stallone and the IBM team scaled Granite Code Models by organizing training data using topological sorts. By ensuring that definitions appear before their references in the training stream, the model better learns the logical flow and cross-file relationships inherent in professional software.
The Risks of Cascading Failure
While topological ordering is a powerful heuristic, it is not a silver bullet. Wenting Zhao and the authors of the Commit0 benchmark point out a critical vulnerability: if a foundational module is implemented incorrectly, the error can cascade through the entire graph. In some cases, a non-linear implementation order might allow an agent to "look ahead" and adjust the base logic to fit the needs of the high-level features.
Despite these challenges, the shift from linear text generation to graph-based synthesis marks a transition in AI coding from simple autocomplete to genuine software engineering. By respecting the structural dependencies of code, these frameworks allow LLMs to build systems that are not just syntactically correct, but architecturally sound.