HullFT: Geometric Test-Time Finetuning via Convex Hulls and Gradient Reuse

Paper: 2605.30337 Authors: Alaa Khamis, Alaa Maalouf Categories: cs.LG

The Gap

Test-time finetuning (TTFT) adapts language models per query by retrieving related examples and updating weights before inference. Existing methods face a quality-speed dilemma: fast nearest-neighbor retrieval often grabs redundant examples (high overlap, low diversity), while diversity-aware selection methods like determinantal point processes are too slow for per-query use. The core tension is that retrieval happens in the critical path—every millisecond counts, but naive speed sacrifices adaptation quality.

Problem: TTFT needs both speed and diversity
   |
   v
Existing approaches split:
   |
   +---> Fast retrieval (k-NN)  ---> Redundant examples ---> Weak adaptation
   |
   +---> Diverse selection (DPP) ---> Slow per-query ---> Impractical
   |
   v
This paper's path:
   Geometric projection (Frank-Wolfe on convex hull)
   |
   v
   Sparse support set (relevant + diverse)
   |
   v
   Integer multiset via geometric rounding
   |
   v
   Gradient reuse across repeated examples
   |
   v
   Result: Better quality at lower total cost

The Increment

One sentence: Before HullFT, you chose between fast-but-redundant retrieval or slow-but-diverse selection; after HullFT, geometric projection gives you both by representing queries as sparse convex combinations of training points, with gradient caching turning repeated examples into a computational advantage.

Core Mechanism

HullFT has three stages. First, given a query embedding, it finds a sparse convex combination of training embeddings that reconstructs the query—think of it as expressing the query as a weighted average of a few training points. This uses Frank-Wolfe optimization, which iteratively adds the training point with the highest inner product to the current mixture. The sparsity constraint ensures only a small support set is selected, and the convex hull geometry naturally enforces diversity (points far apart in embedding space contribute more to reconstruction).

Second, the fractional weights from the convex combination (e.g., 0.3, 0.5, 0.2) need to become integer counts for finetuning. HullFT uses a geometric integerization procedure that rounds these weights to integers while preserving the total budget and minimizing distortion. This produces a multiset—some examples appear multiple times.

Third, during finetuning, HullFT exploits the repeated examples. Instead of recomputing gradients for each occurrence, it caches the gradient from the first pass and reuses it for subsequent identical examples. This amortizes the forward-backward cost across repetitions, making the finetuning step faster without sacrificing quality.

Query embedding q
   |
   v
[Frank-Wolfe on convex hull]
   Find: q ~= w1*e1 + w2*e2 + ... + wk*ek
   where e_i are training embeddings, w_i >= 0, sum(w_i) = 1
   |
   v
Sparse support: \{(e1, w1), (e2, w2), ..., (ek, wk)\}
   |
   v
[Geometric integerization]
   Round weights to integers: \{(e1, n1), (e2, n2), ...\}
   |
   v
Multiset for finetuning: [e1, e1, ..., e2, e2, ..., ek, ...]
   |
   v
[Gradient caching]
   First pass on e1: compute gradient g1, cache it
   Subsequent passes on e1: reuse g1 (skip forward-backward)
   |
   v
Updated model -> Evaluate query

Think of HullFT as budget allocation in a portfolio. You have a query (your investment goal) and a universe of training examples (available assets). The convex hull projection is like finding the minimal set of assets whose weighted combination matches your goal—you want few assets (sparsity) that are complementary (diversity), not redundant. The fractional weights are your ideal allocation percentages, but you can only buy whole shares, so you round them to integers (integerization). Finally, when you execute the trades, if you’re buying multiple shares of the same asset, you don’t recalculate its value each time—you cache the first calculation and reuse it (gradient caching). The portfolio metaphor maps directly: query ↔ goal, training examples ↔ assets, convex weights ↔ allocation, integerization ↔ whole shares, gradient reuse ↔ cached valuation.

Key Concepts

• Convex hull and sparse reconstruction: Imagine you’re standing in a room and want to describe your position using only a few landmarks. The convex hull is the smallest “tent” stretched over all landmarks—any point inside can be expressed as a weighted average of the tent’s corners. Sparse reconstruction means using as few landmarks as possible. In HullFT, the query embedding is your position, training embeddings are landmarks, and Frank-Wolfe finds the minimal set of landmarks (and their weights) that pinpoint your location. This is powerful because landmarks far apart naturally contribute more (diversity), while nearby redundant landmarks get zero weight (relevance without redundancy).

• Frank-Wolfe optimization: Standard optimization methods (like gradient descent) take small steps in the direction that improves the objective. Frank-Wolfe is different: at each step, it solves a simpler linear problem (find the single best point to add) and moves toward that point. It’s “projection-free” because you never need to explicitly project onto the constraint set—you just pick from the vertices. For HullFT, this means each iteration adds one training example (the one with highest similarity to the current residual), making it naturally sparse and fast. Concrete example: if your query is “explain quantum entanglement,” and you’ve already selected a physics textbook excerpt, Frank-Wolfe next picks the example that best covers what’s still missing—maybe a simple analogy—rather than another physics textbook.

• Gradient reuse: In standard finetuning, if you train on the same example twice, you compute its gradient twice—wasteful. Gradient reuse caches the gradient from the first pass and reuses it for subsequent identical examples. This works because the gradient depends only on the example and the current model state; if the example is the same and you’re in the same finetuning batch, the gradient is the same. Concrete example: if your multiset has “example A” three times, you do one forward-backward pass for A, cache the gradient, then apply it three times. You’ve turned three expensive operations into one expensive + two cheap operations.

Framework Shift

Before (mainstream TTFT):              After (HullFT):

Query q                                Query q
  |                                      |
  v                                      v
k-NN retrieval                         Convex hull projection
  |                                      |
  +---> Top-k similar examples          +---> Sparse support set
        (often redundant)                     (relevant + diverse)
  |                                      |
  v                                      v
Finetune on all k                      Integerize weights
  (each example once)                    |
  |                                      v
  v                                    Multiset with repetitions
Evaluate query                           |
                                         v
                                       Finetune with gradient reuse
                                         (amortize computation)
                                         |
                                         v
                                       Evaluate query

From similarity-based retrieval to geometry-based reconstruction, the core shift is treating selection as a sparse approximation problem in embedding space rather than a ranking problem.

Expert Assessment

Problem choice: Real gap. TTFT is gaining traction (see recent work on in-context learning and retrieval-augmented generation), and the speed-quality tradeoff is a genuine bottleneck for deployment. The problem sits at the intersection of efficient adaptation and geometric optimization—timely and well-motivated.

Method maturity: Clever insight, not brute force. The convex hull framing is elegant and theoretically grounded. However, the paper could explore simpler baselines more thoroughly—what about greedy diversity heuristics (e.g., maximal marginal relevance) that don’t require convex optimization? Frank-Wolfe is efficient, but the comparison against lightweight diversity methods feels incomplete.

Experimental integrity: Baselines are reasonable (k-NN, DPP-based selection), and the bits-per-byte metric is appropriate for language modeling. The runtime measurements are honest—they include both selection and finetuning time, which is critical. One red flag: the experiments are on relatively small models and datasets. Scaling behavior to billion-parameter models and web-scale retrieval corpora is unclear. The gradient reuse speedup is real but depends on having repeated examples—what happens when the support set is already diverse enough that integerization produces mostly unique examples?

Writing quality: The paper is dense and assumes familiarity with convex optimization. The Frank-Wolfe section could use a worked example with actual numbers. The integerization procedure is described algorithmically but lacks intuition—why this rounding scheme over simpler alternatives? The related work section is thorough but could better position HullFT relative to recent retrieval-augmented methods outside TTFT (e.g., RETRO, Atlas). Rewriting Section 3.2 (integerization) with a visual example would elevate clarity significantly.

Verdict: weak accept — Solid contribution with a novel geometric angle and practical speedups, but needs stronger evidence of scaling and clearer exposition of the integerization step.

Takeaways

Sparse convex reconstruction as a selection primitive: The idea of representing a query as a sparse convex combination of candidates is broadly applicable beyond TTFT. Anytime you need to select a small, diverse subset from a large pool (e.g., active learning, coreset construction, prompt selection for few-shot learning), framing it as sparse reconstruction over a convex hull gives you relevance and diversity in one shot. Frank-Wolfe makes it tractable.

Gradient caching for repeated data: If your training loop naturally produces repeated examples (data augmentation, oversampling, or multiset-based selection), caching gradients is a simple, high-impact optimization. This transfers directly to any scenario where you control the data distribution and can identify duplicates—think curriculum learning with repeated hard examples or federated learning with overlapping client data.

Integerization as a design pattern: The problem of converting fractional weights to integer counts while preserving structure appears in many contexts—sampling from distributions, resource allocation, rounding linear program solutions. The geometric integerization here (minimizing distortion in embedding space) is a specific instance, but the pattern is reusable: define a distortion metric in your domain, then round to integers while minimizing that metric.