Context Composition¶

Every iteration, the LLM sees a subset of the full graph --- selected, scored, and positioned to maximize information value within a fixed token budget. This is the context composition pipeline, running in agent loop steps 4--6. Personalized PageRank expands from the current task, entropy-adaptive scoring ranks candidates, a submodular knapsack packs the best set, and U-shape positioning places the most important items where attention is strongest. The key product effect: as budget pressure rises and evidence converges, the context shifts from exploratory breadth to goal-focused depth --- without any prompt change.

The pipeline addresses a fundamental challenge in iterative reasoning: the graph grows with each iteration, but the LLM's context window is fixed. Naive approaches (include everything, or include the most recent) either overflow the budget or miss critical context from earlier iterations. The composition pipeline solves this by treating context selection as a budgeted submodular maximization problem --- selecting the subset of nodes that maximizes a diversity-aware relevance objective under a token cost constraint.

Pipeline Overview¶

flowchart LR
    Task["Selected Task"] --> PPR["PPR Expansion<br/><small>seed → neighbors → ranked</small>"]
    PPR --> Score["Entropy-Adaptive<br/>Scoring<br/><small>GA + PPR blend</small>"]
    Score --> Pack["Submodular<br/>Knapsack<br/><small>MIG density</small>"]
    Pack --> Position["U-Shape<br/>Layout<br/><small>head / bulk / tail</small>"]
    Position --> DIN["DIN-Read<br/>Serialization"]

The pipeline is deterministic and LLM-free. AdaGReS beta computation uses a fixed-seed RNG (seed=42) when candidates exceed 200, making it reproducible but not purely algebraic for large candidate sets.

PPR Expansion¶

Personalized PageRank (PPR), introduced by Page et al. (1998) and extended to machine learning by Klicpera et al. (2019), discovers relevant nodes by simulating a random walk from seed nodes with teleportation back to seeds at each step. Unlike standard PageRank, which measures global importance, PPR measures importance relative to a specific set of seed nodes --- in Lethe's case, the current task and its immediate context.

Seed Selection¶

Seeds are derived from the current iteration context:

• Current task — the task being worked on
• Parent task — provides hierarchical context
• Terminal children — completed or failed subtasks whose results inform the current task

Each seed receives a weight proportional to its goal alignment squared plus a constant floor:

Squaring amplifies high-GA seeds. The floor prevents zero-weight seeds from being entirely excluded from the random walk.

Transition Matrix¶

Transition probabilities between nodes use softmax over logits:

with temperature \(\tau = 3.0\). For structural edges (SUBTASK_OF, DEPENDS_ON, PRODUCED), \(\kappa_{ij} = \text{normalize\_cosine}(\cos(\mathbf{e}_i, \mathbf{e}_j))\).

For SIMILAR_TO edges enriched with NLI scores, the logit uses the NLI kernel:

where \(h = \text{support} \cdot (1 - \text{contra})\). Contradiction penalizes both the NLI term and the cosine fallback, so contradicting neighbors are universally suppressed. When \(c = 0\) (no NLI confidence), \(\kappa\) degrades to \(\text{sim} \cdot (1 - \text{contra})\).

Power Iteration¶

PPR runs power iteration with damping factor 0.85 (standard value from the original PageRank paper). At each step, a fraction \((1 - d) = 0.15\) of probability mass teleports back to seed nodes, while the remainder follows the transition matrix.

Dangling nodes (those with no outgoing edges) redistribute their mass to seeds rather than uniformly — this biases the walk toward task-relevant regions rather than random graph locations.

The top-\(k\) nodes by PPR score become CandidateNode entries for scoring.

Entropy-Adaptive Scoring¶

PPR expansion produces a ranked set of candidate nodes. The scoring stage blends PPR's structural relevance with goal alignment from the embedding algebra, adapting the balance based on how much information entropy remains in the evidence pool:

Before scoring, a hard cap of 10,000 candidates prevents pathological scaling on very large graphs. Unembedded nodes receive a neutral similarity of \(0.5^2 = 0.25\) as their PPR seed weight, ensuring they participate in expansion without dominating embedded nodes.

Candidates are scored using a dynamic blend of goal alignment (GA) and PageRank (PR), where the blend ratio adapts to the diversity of the PPR distribution.

Entropy Shift¶

where \(H_{\text{norm}}\) is the normalized entropy of the PPR score distribution. When PPR scores are uniformly spread (high entropy), the shift increases the GA weight — the random walk is uninformative, so goal alignment must compensate. When PPR concentrates on a few nodes (low entropy), the walk is decisive and PR dominates.

Pressure Shift¶

Budget pressure quadratically increases GA weight. Under pressure, the system aggressively prefers goal-aligned content over structurally central content.

Final Score¶

The \(\epsilon = 0.01\) floor prevents zero scores from excluding nodes entirely.

Submodular Knapsack¶

Scored candidates must be packed into a fixed token budget. A naive top-k by score would cluster related evidence together, wasting tokens on redundant information. The submodular knapsack solves this by greedily selecting candidates that maximize marginal information gain --- each new item is evaluated by how much it adds beyond what is already selected, not by its standalone score.

This approach is adapted from Lin and Bilmes (NAACL 2010), who showed that multi-document summarization can be formulated as budgeted maximization of a submodular function. A function \(f\) is submodular if adding an element to a smaller set yields at least as much gain as adding it to a larger set (diminishing returns). The greedy algorithm that selects the element with the highest gain-to-cost ratio at each step achieves a \((1 - 1/e) \approx 0.632\) approximation ratio for monotone submodular objectives under a budget constraint.

AdaGReS Beta¶

The redundancy penalty \(\beta\) adapts to the diversity of the candidate pool:

where \(\bar{d}\) is the mean pairwise geodesic distance (arccos of cosine similarity, divided by \(\pi\)) and \(d_{\max}\) is the maximum. Defaults: \(\beta_{\min} = 0.3\), \(\beta_{\max} = 0.7\).

• Homogeneous pool (low \(\bar{d}/d_{\max}\)) → low \(\beta\) → accepts similar items (redundancy is unavoidable).
• Diverse pool (high \(\bar{d}/d_{\max}\)) → high \(\beta\) → penalizes similar items (diversity is achievable and valuable).

Incremental MIG¶

For each candidate, the marginal gain uses a multiplicative redundancy penalty --- the relevance is scaled down rather than subtracted:

The multiplicative form ensures low-relevance items can never achieve negative marginal gain, keeping the objective monotone. The density (value per token) is:

At each step, the candidate with highest density is added to the selected set. If adding the best candidate would exceed the token budget, it is skipped and smaller candidates are tried. If no candidates fit, the algorithm terminates.

Fallback: If the greedy process fails to select any candidates (all too large for the budget), the single candidate with highest raw relevance score is selected and truncated to fit.

Verbosity Tiers¶

All selected nodes start at VERBATIM. If the packed set exceeds the token budget, nodes are downgraded to GIST (first sentence only) in reverse density order until the set fits.

Two levels only — VERBATIM (full) and GIST (first sentence). The middle "summary" tier (arbitrary mid-text truncation) was removed as low-value over-engineering that produced garbled half-content.

U-Shape Positioning¶

Selected nodes are positioned in the context window following a U-shape attention pattern: the most important items appear at the head and tail, where LLM attention is empirically strongest. The resulting order drives DIN-Read serialization.

flowchart LR
    subgraph head ["Head — High Attention"]
        Goal["Goal Task<br/><small>verbatim</small>"]
        Deps["Dependencies<br/><small>ordering context</small>"]
    end

    subgraph bulk ["Bulk — Standard"]
        PPR1["PPR-Ranked<br/>Evidence"]
        PPR2["PPR-Ranked<br/>Tasks"]
    end

    subgraph tail ["Tail — High Attention"]
        Current["Current Task<br/><small>verbatim, full evidence</small>"]
    end

    head ~~~ bulk ~~~ tail

Position Assignment Rules¶

The current task is always included at VERBATIM level regardless of its MIG score — the agent must have full visibility into what it is currently working on.

Token Budget¶

The context window budget is a configurable fraction of the LLM's total context length:

Default context_ratio is 0.55, and din_framing_tokens is 150 (overhead for DIN-Read formatting). With the default 49K context: int(49152 × 0.55) − 150 = 26,883 tokens for packed content.

Token estimation uses a character-based heuristic (~3 characters per token) rather than actual tokenization — fast and sufficiently accurate for budget allocation. The exact token count is managed by the LLM server's context handling.

Integration with Iteration Cycle¶

Context composition runs once per iteration as steps 4--5 of the agent loop. The resulting PositionedSubgraph is passed to DIN-Read serialization (step 6), which converts node objects into the text format the LLM receives.

Budget pressure from the budget manager flows into the scoring step via the pressure_shift, causing late-stage iterations to favor goal-aligned evidence over structurally central content. This means the context naturally shifts from exploratory (broad, PPR-driven) to focused (narrow, GA-driven) as the session progresses --- without any explicit prompt change.

References¶

• Page, L. et al. "The PageRank Citation Ranking." Stanford InfoLab, 1998 --- Lethe uses the personalized variant with cosine-weighted transitions.
• Klicpera, J. et al. "Predict then Propagate: Graph Neural Networks meet Personalized PageRank." ICLR, 2019 --- Decoupled PPR propagation; Lethe applies PPR as context expansion rather than node classification.
• Lin, H. and Bilmes, J. "Multi-document Summarization via Budgeted Maximization of Submodular Functions." NAACL, 2010 --- Greedy submodular knapsack with \((1 - 1/e)\) guarantee.
• Carbonell, J. and Goldstein, J. "MMR Diversity-Based Reranking." SIGIR, 1998 --- The redundancy-penalized objective MIG generalizes.
• Liu, N.F. et al. "Lost in the Middle." TACL, 2024 --- U-shape attention pattern motivating head/tail positioning.
• Gutiérrez, B.J. et al. "HippoRAG: Neurobiologically Inspired Long-Term Memory for Large Language Models." 2024 --- PPR over knowledge graphs for multi-hop reasoning; Lethe extends this with submodular packing and budget-adaptive scoring.
• S-RAG. "Optimal Document Selection in RAG via Combinatorial Optimization." NeurIPS, 2025 --- Formalizes RAG context selection as monotone submodular maximization under knapsack constraint.
• AdaGReS. "Adaptive Greedy Context Selection." 2024 --- Adaptive redundancy penalty with closed-form \(\beta\) calibration responding to candidate pool diversity.
• Lee, D. et al. "SetR: Shifting from Ranking to Set Selection for RAG." 2025 --- Argues RAG needs set-level coverage, not pointwise reranking. Decomposes a query into information requirements and selects a complementary passage set. Parallel to Lethe's MIG knapsack but LLM-guided; complements the greedy submodular approach.