Topological Prompt Ordering for Language Models

23 concepts16 papers1 proposal

When feeding a large codebase or a collection of research papers into a Large Language Model (LLM), the standard approach is to flatten the files into a single linear sequence. Files are typically concatenated alphabetically, by directory structure, or via arbitrary retrieval ranking.

However, software repositories and academic literature are inherently structured as directed graphs: functions call other functions, source files import modules, and scientific papers cite earlier discoveries. When an autoregressive language model processes a naively flattened prompt, it frequently encounters references to entities it has not yet seen. This structural mismatch forces the model to reason about complex dependencies without foundational context, leading to hallucinations, type mismatches, and a breakdown in long-context understanding.

To bridge this gap, a prominent research direction utilizes static analysis to map out the underlying Directed Acyclic Graph (DAG) of dependencies and sequences the prompt using a topological sort. By ensuring that definitions precede references and independent components precede their dependents, this technique aligns the input context with the causal processing mechanics of modern transformers.

The Core Intuition: Aligning Context with Causality

Why does topological prompt ordering work so effectively? The answer lies in how autoregressive language models compute attention.

Transformers process tokens sequentially from left to right. When a model generates or analyzes a token, it can only attend to information that has already appeared earlier in the sequence. If a prompt introduces a high-level function before defining the low-level utilities it calls, the model's key-value (KV) cache lacks the necessary grounding when the function signature is first processed.

Naive Flattening (Alphabetical/Arbitrary):
[ High-Level Caller ] ---> [ Low-Level Utility (Unknown to Caller) ] ❌

Topological Ordering:
[ Low-Level Utility ] ---> [ High-Level Caller (Attends to Utility) ]  | Populates KV Cache

By sorting files or code blocks topologically, upstream dependencies are guaranteed to occupy the earlier slots of the input sequence. As Yang et al. demonstrate in Hierarchical Context Pruning: Optimizing Real-World Code Completion with Repository-Level Pretrained Code LLMs, placing imported modules before the active file aligns the prompt structure with both the causal nature of LLMs and the logical flow of software compilers. This structural alignment dramatically improves the model's ability to resolve references and complete code accurately while minimizing prompt bloat.

This principle extends beyond code completion to repository-scale understanding. For instance, in RepoQA: Evaluating Long Context Code Understanding, Liu et al. concatenate source files by sorting them according to their global dependency graph, ensuring that the model processes definitions before references to maintain a coherent logical flow across thousands of lines of code.

Bottom-Up Processing and Incremental Context Aggregation

For complex tasks like repository summarization and documentation, topological sorting enables a powerful execution paradigm: bottom-up incremental context construction.

Instead of forcing a model to understand an entire codebase simultaneously, systems can traverse a call graph from the leaf nodes (independent functions) up to the root nodes (complex callers). The model first summarizes or documents the independent leaf functions. Because these summaries are generated early, they can be systematically injected into the prompt context when the model moves up the graph to process parent functions.

       [ Root Function ]         (Processed last, using Leaf & Mid summaries)
             /   \
     [ Mid-Level ]  \            (Processed second, using Leaf summary)
         /            \
  [ Leaf Function A ]  [ Leaf Function B ] (Processed first, independent)

This recursive strategy allows the model to digest intricate hierarchical code structures through localized, step-by-step information aggregation. This mechanism is leveraged across several specialized frameworks:

Preventing Cascading Errors in Code Translation

Topological sequencing is equally vital when language models are tasked with modifying or translating codebases. If an LLM agent refactors or translates a high-level component before updating its underlying dependencies, it will likely generate code based on outdated signatures. When the base dependencies are eventually modified later, the previously generated high-level code becomes invalid. Cheng et al. refer to this frustrating cycle of broken references as the "whack-a-mole" problem in Escaping Whack-a-Mole: Optimizing Documentation as Repo-Specific Playbooks for Coding Agents.

By enforcing a strict dependency-guided sequence, developers can achieve a monotonic improvement in code generation correctness. Low-level dependencies are stabilized first, ensuring that their finalized signatures are available in the prompt context when high-level callers are addressed.

This architectural pattern underpins several recent breakthroughs in automated software engineering:

  • Project-Scale Transpilation: Tools designed to migrate entire codebases to safe languages—such as SACTOR (Zhou et al.), RustMap (Cai et al.), and Oxidizer (Zhang et al.)—decompose source projects into dependency graphs of types and functions. This ensures that upstream data structures are translated and validated before downstream modules are processed.
  • Scientific Code Migration: In Systematic LLM Translation of Legacy Scientific Code to Differentiable Frameworks: Application to a Land Surface Model, Lahlou et al. demonstrate that translating complex scientific codebases requires a topological ordering of modules. Without this context, LLMs frequently fail due to hallucinated types or incorrect assumptions about external modules.
  • Memory Safety Refactoring: The Memory Safety Assistant (MSA) framework introduced by Mohammed et al. decomposes whole-program transformations by constructing a dependency graph of top-level declarations and processing them via a reverse topological sort, making updated signatures immediately available to dependent functions.
  • Context Window Relief: As Ibrahimzada notes in Program Decomposition and Translation with Static Analysis, decomposing large files into individual methods and translating them bottom-up via a call graph drastically reduces the "out-of-context" problem, freeing up valuable prompt space.

Application to Non-Code Domains: Citation Networks

While topological prompt ordering is naturally suited to code due to explicit abstract syntax trees and call graphs, the underlying mechanism applies to any context that can be modeled as a directed network.

A prime example is academic literature, where papers are linked by citation networks. Historically, models trained on multi-document tasks were fed papers in an arbitrary or chronological order. In Improving Referring Ability for Biomedical Language Models, Jiang et al. introduce LinkLM, a strategy that organizes biomedical research papers into training sequences based on their citation graphs.

By placing cited or supporting documents before the target document—a concept the authors call causal context ordering—the language model is forced to utilize previously processed information as an explicit reference for predicting tokens in the current document. This simple topological restructuring significantly strengthens the model's cross-document referring and in-context learning capabilities.

Whether applied to a low-level helper function, a repository-level import, or a biomedical citation, the core takeaway remains identical: structuring the prompt to mirror the causal flow of dependencies allows autoregressive language models to process complex, interconnected information exactly as they were designed to do.

Key Foundational Work

MALSIGHT: Exploring Malicious Source Code and Benign Pseudocode for Iterative Binary Malware Summarization (2024) — contributed 2 concept elements to this direction.
Automated detection of api refactorings in libraries (2007) — contributed 2 concept elements to this direction.
Improving Referring Ability for Biomedical Language Models (2024) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_topological_prompt_ordering_de110402,
  title = {topological prompt ordering},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/topological-prompt-ordering/rdr_de110402db7c44cfb6fa4707c52d9eb3},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_topological_prompt_ordering_de110402_v1,
  title = {topological prompt ordering},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/topological-prompt-ordering/rdr_de110402db7c44cfb6fa4707c52d9eb3/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake