Budget-Aware Routing for Long Clinical Text

1. Problem Statement

Large Language Models (LLMs) face significant deployment challenges in clinical settings due to the high cost and latency associated with processing long, heterogeneous, and redundant inputs (e.g., discharge notes, radiology reports).

• The Constraint: Clinical systems operate under strict token budgets ($B$) to control monetary costs ($p_{in} \times B$) and inference latency.
• The Challenge: The input documents are often thousands of tokens long, while downstream tasks (like summary generation) are short and high-stakes.
• The Goal: To select a subset of document units under a strict token budget such that an off-the-shelf generator can meet fixed cost and latency constraints while maximizing downstream utility (relevance, coverage, and diversity).
• Formulation: The authors cast this as a knapsack-constrained subset selection problem, where the objective is to maximize a utility function subject to a token cost limit.

2. Methodology

The proposed framework treats context construction as an explicit module decoupled from the generator. It consists of four stages:

A. Unitization Strategies

The system segments the long document $D$ into selectable units ($u_1, \dots, u_n$) with associated token costs ($c_i$). Four strategies are evaluated:

1. Sentence-Unit: Splits at sentence boundaries (maximum flexibility).
2. Section-Unit: Groups sentences by section headers (e.g., "Chief Complaint").
3. Window-Unit: Creates overlapping chunks based on local content density.
4. Cluster-Unit: Groups semantically related sentences using a similarity graph.

B. Selection Algorithms

The system employs various selectors to choose the optimal subset $S$ within budget $B$:

• Baselines:
  • Lead: Selects units from the start of the document (exploits front-loading).
  • Shuffled: Randomizes order to measure positional bias.
  • Sliding: Selects the contiguous sequence with highest relevance.
  • Hierarchical: Adds context around high-relevance anchors.
  • GraphCluster: Selects representatives from semantic clusters.
• Diversity-Aware:
  • MMR (Maximal Marginal Relevance): Iteratively balances relevance against redundancy using a similarity kernel.
  • RCD (Relevance-Coverage-Diversity): A novel monotone submodular objective defined as:
    $$F(S) = \alpha R(S) + \beta C(S) + \gamma D(S)$$
    Where $R$ is relevance to the query, $C$ is facility-location coverage (representing the whole document), and $D$ is log-determinant diversity. This allows for approximation guarantees under knapsack constraints via lazy greedy selection.

C. Budget-Aware Routing

The authors propose a lightweight heuristic that dynamically selects the best algorithm based on the budget regime ($B$) and document statistics:

• Low Budget ($B \le B_1$): Uses Lead (positional heuristics work well when content is front-loaded and budgets are tight).
• Moderate Budget ($B_1 < B \le B_2$): Uses MMR (redundancy becomes the limiting factor; diversity is needed).
• High Budget ($B > B_2$): Uses RCD (coverage becomes the priority to represent diverse topics).
• Metrics for Routing: Uses a front-loading index ($\phi$) and a redundancy index ($\rho$) to inform decisions.

3. Key Contributions

1. Formalization: Defined budgeted context construction as a knapsack-constrained optimization problem with explicit unitization and selection stages.
2. RCD Objective: Introduced a submodular objective function that explicitly balances relevance, coverage, and diversity.
3. Unified Selector Suite: Implemented and compared a comprehensive family of selectors (Lead, MMR, RCD, etc.) across multiple unitization strategies.
4. Routing Heuristic: Developed a budget-aware router that adapts the selection strategy to the token budget, achieving near-oracle performance.
5. Comprehensive Evaluation: Conducted experiments across three distinct datasets:
   • MIMIC-IV: Clinical discharge notes.
   • Cochrane: Scientific abstracts.
   • L-Eval: Long-document benchmarks.
   • PubMedQA: Classification task (to test generalization beyond summarization).

4. Key Results

A. Evaluation Paradigm Dependence

The optimal strategy depends heavily on whether the task is extractive (selecting text to match a reference) or generative (LLM summarization):

• Extractive Tasks: Lead (positional) dominates at low budgets because clinical notes front-load critical info, and ROUGE rewards lexical overlap.
• Generative Tasks (LLM): MMR and RCD consistently outperform Lead. LLMs benefit from non-redundant input; removing repetitive boilerplate allows the model to focus on salient concepts, even if the exact words differ from the reference.

B. Metric Sensitivity

• ROUGE: Saturates quickly for LLM summaries (scores plateau around 0.27–0.28) because LLMs paraphrase rather than copy, reducing lexical overlap.
• BERTScore: Better differentiates method quality. It captures semantic similarity, showing that diversity-aware methods (MMR) produce more semantically appropriate summaries than positional methods, even when ROUGE scores are similar.

C. Unitization vs. Selection

• Selector Choice > Unitization: The choice of selection algorithm (e.g., MMR vs. Lead) matters significantly more than the unitization strategy (Sentence vs. Section).
• Cluster-Unit Failure: Cluster-based grouping reduced performance, likely because it created units that were too large for fine-grained selection or disrupted the temporal narrative of clinical notes.

D. Routing Performance

• The proposed routing heuristic closely tracks the oracle upper bound (the best possible method for a specific instance).
• At 512 tokens (approx. 25% of median document length), budgeted selection with MMR matched or exceeded the performance of processing the full context with GPT-4o, demonstrating significant cost savings without quality loss.
• Generalization: On PubMedQA (where information is not front-loaded), Lead performed worst, and RCD/MMR excelled, proving the framework adapts to non-front-loaded documents.

5. Significance and Implications

• Cost Efficiency: The study proves that principled selection can reduce token usage by ~75% (e.g., 512 vs. 2000+ tokens) while maintaining or improving generation quality, offering substantial economic savings for hospital-scale deployments.
• System Design: It shifts the paradigm from "long-context models" to "budget-aware context construction," suggesting that the bottleneck is often the input construction rather than the model's context window size.
• Practical Guidelines:
  • Use positional heuristics (Lead) for tight budgets in extractive tasks.
  • Use diversity-aware methods (MMR/RCD) for generative tasks to filter redundancy.
  • Use semantic similarity metrics (BERTScore) rather than just ROUGE for evaluating LLM summaries.
• Ethical Considerations: The authors highlight that budgeting is a "lossy" process. They advocate for provenance tracking (linking generated claims to source sentences) and dynamic budget escalation for high-risk clinical cases to ensure safety.

In conclusion, the paper provides a rigorous, system-level approach to managing LLM costs in clinical settings, demonstrating that adaptive routing based on budget constraints can significantly optimize performance across diverse document types and task objectives.