How contextwindow.Pack() Uses BM25 Relevance Scoring to Fit Context Into a Token Budget

The Pack() function in JuliusBrussee/caveman combines Okapi BM25 relevance scoring with priority, recency, and error signals to deterministically select the most valuable context fragments until the token budget is exhausted.

The contextwindow package in the JuliusBrussee/caveman repository solves the critical problem of fitting expansive contextual data into an LLM's limited prompt window. Located in engine/contextwindow/contextwindow.go, the Pack() method implements a deterministic, offline algorithm that treats context selection as an information retrieval problem, using classic BM25 ranking augmented with domain-specific signals to maximize prompt value within strict token constraints.

BM25 Relevance Scoring Foundation

At the core of the ranking algorithm lies a deterministic implementation of Okapi BM25. For every candidate item, Pack() calculates relevance by comparing the query string against the item's text using the bm25Scores function.

According to the source code in engine/contextwindow/contextwindow.go (lines 73-85), the implementation uses standard BM25 parameters: k1=1.5 and b=0.75. These values control term frequency saturation and document length normalization respectively, ensuring that longer context fragments do not unfairly dominate shorter, more concise entries. The scoring operates entirely offline, requiring no external API calls or stochastic sampling.

Composite Scoring Architecture

Raw BM25 scores alone do not capture business priorities or temporal urgency. Pack() augments relevance with four additional signals computed for each candidate in engine/contextwindow/contextwindow.go (lines 108-120).

Priority Weighting

The system adds item.Priority directly to the BM25 score, allowing explicit business logic to override pure textual relevance. High-priority items receive a deterministic boost regardless of their semantic similarity to the query.

Temporal Recency Decay

Items decay exponentially based on the time difference between opts.Now and the item's Timestamp, weighted by opts.RecencyWeight (lines 108-114). This ensures recent events surface even if their BM25 scores are marginally lower than older, more keyword-dense fragments.

Error Keyword Boosting

When text matches common error keywords such as ERROR or FATAL, the algorithm adds a fixed opts.ErrorBoost value (lines 115-117). This semantic signal helps critical failure states punch through the ranking despite generic query terms.

Pinning Critical Items

Items marked with Pin: true receive an extremely large constant score of 1,000,000 (lines 118-120). This guarantee ensures mission-critical context fragments always appear in the final selection, effectively bypassing the competitive ranking process.

Token Accounting and Budget Management

Before packing begins, Pack() ensures accurate token counts. If an item's Tokens field equals zero, the function counts tokens on-the-fly using the supplied tokens.Counter from engine/tokens/tokens.go (lines 94-101). This lazy evaluation prevents redundant computation while ensuring precise budget enforcement.

Default options apply sensible fallbacks if the caller omits parameters like MaxTokens or RecencyWeight (lines 70-81).

Greedy Selection Algorithm

After computing composite scores, Pack() sorts candidates in descending order while preserving original index ties to ensure deterministic output (lines 123-128).

The algorithm then iterates greedily through the sorted list (lines 130-141). For each item, it checks if the token count fits within the remaining budget calculated as opts.MaxTokens - opts.ReserveTokens. Items fitting within the budget are selected immediately; those exceeding available tokens are skipped. This greedy approach guarantees optimal packing for the composite score metric without expensive knapsack computations.

Result Construction and Chronological Reordering

Selected items undergo a final transformation in engine/contextwindow/contextwindow.go (lines 144-154). Despite being selected by relevance score, the returned items are reordered to their original chronological sequence. The function returns a Result struct containing the chosen items, total token usage statistics, and a count of deferred items that exceeded the budget.

Practical Implementation Examples

The following examples demonstrate typical usage patterns for the Pack() function.

// Example: Packing recent log entries around a user query
items := []contextwindow.Item{
    {ID: "1", Text: "Server started successfully", Timestamp: time.Now().Add(-2 * time.Hour)},
    {ID: "2", Text: "ERROR: Database connection failed", Timestamp: time.Now().Add(-30 * time.Minute), Priority: 0.2},
    {ID: "3", Text: "User login succeeded", Timestamp: time.Now().Add(-10 * time.Minute)},
}
opts := contextwindow.Options{
    MaxTokens:       500,
    RecencyWeight:   0.2,
    ErrorBoost:      1.0,
    Now:             time.Now(),
}
result := contextwindow.Pack("database error", items, opts)

// `result.Items` now contains the error log (boosted) and any other
// items that fit within the 500-token budget, ordered chronologically.

// Example: Forcing inclusion of a pinned item
items := []contextwindow.Item{
    {ID: "a", Text: "Important system notice", Pin: true},
    {ID: "b", Text: "Routine health check"},
}
result := contextwindow.Pack("", items, contextwindow.Options{})
// The pinned item will always appear in `result.Items` regardless of token budget.

Summary

• BM25 Foundation: contextwindow.Pack() uses Okapi BM25 with k1=1.5 and b=0.75 in engine/contextwindow/contextwindow.go to calculate base relevance between queries and candidate text.
• Multi-Factor Scoring: The algorithm combines BM25 with priority weights, exponential recency decay, error keyword boosts, and pinning guarantees to create a composite ranking.
• Deterministic Selection: Items are greedily packed by composite score until the token budget (minus reserved tokens) is exhausted, ensuring reproducible results.
• Lazy Tokenization: Zero-token items trigger on-the-fly counting via engine/tokens/tokens.go, while defaults apply automatically for omitted options.
• Chronological Output: Final results restore original temporal ordering despite relevance-based selection during the packing phase.

Frequently Asked Questions

What is BM25 and why does contextwindow.Pack() use it?

BM25 is a probabilistic ranking function used in information retrieval to estimate the relevance of documents to a given search query. The Pack() method uses Okapi BM25 because it provides a deterministic, well-tested statistical foundation for comparing text relevance without requiring machine learning inference or external API dependencies.

How does the pinning mechanism ensure critical items are always included?

When an item has Pin: true, the algorithm adds a fixed constant of 1,000,000 to its composite score in engine/contextwindow/contextwindow.go (lines 118-120). This value dwarfs typical BM25 scores and other signals, ensuring pinned items rank first in the sorted list and are selected before any non-pinned candidates during the greedy packing phase.

What happens if an item's token count is not pre-calculated?

If item.Tokens equals zero, Pack() invokes the provided tokens.Counter to count tokens on-the-fly (lines 94-101). This lazy evaluation occurs during the packing loop, allowing callers to omit token pre-calculation while still enforcing the MaxTokens budget constraint accurately.

How does the algorithm handle time-sensitive context?

The system calculates an exponential decay bonus based on the difference between opts.Now and each item's Timestamp, weighted by opts.RecencyWeight (lines 108-114). Recent items receive higher composite scores, causing them to rank above older items with similar BM25 relevance scores unless explicitly deprioritized by other signals.

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