🤖 AI

VineLM: Trie-Based Fine-Grained Control for Agentic Workflows

VineLM is a workflow manager that enables fine-grained, dynamic model selection for agentic workflows by representing feasible executions as an annotated trie and using checkpointing with cascade profiling to optimize the cost-latency-accuracy frontier without exhaustive offline profiling.

Original authors: Nikos Pagonas, Matthew Lou, Tianyi Peng, Dan Rubenstein, Kostis Kaffes

Published 2026-05-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Nikos Pagonas, Matthew Lou, Tianyi Peng, Dan Rubenstein, Kostis Kaffes

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are running a high-stakes detective agency. Your goal is to solve a mystery (the "request") using a team of specialists (the "AI models"). Some specialists are cheap and fast but might miss clues; others are expensive and slow but are brilliant detectives.

In the past, if you hired a detective agency, you had to sign a contract before the investigation started. You had to pick one specific detective for the "Gathering Evidence" phase and one specific detective for the "Fixing Mistakes" phase, and you had to stick with them no matter what happened. If the first detective found a huge clue, you couldn't switch to a cheaper specialist for the next step. If the first detective took too long, you were stuck with the expensive one for the rest of the case, even if you were running out of time.

VineLM is a new way of managing these detective agencies. Instead of signing a rigid contract at the start, VineLM acts like a smart project manager who checks in after every single step and decides: "Given where we are right now, how much time and money do we have left? Who is the best person to do the next specific task?"

Here is how it works, broken down into simple concepts:

1. The Problem: The "One-Size-Fits-All" Trap

Current systems (like the one called Murakkab) are like a manager who picks a "Plan A" before the work begins.

The Flaw: If your plan involves a loop (like "Keep fixing the SQL code until it works"), the old system forces you to use the same detective for every single fix.
The Result: You might use a brilliant (but expensive) detective for the first fix, and then be forced to use that same expensive detective for the second and third fixes, even if the second fix was easy and could have been done by a cheap intern. Or, you might run out of time because the first step took longer than expected, but you can't switch to a faster detective for the remaining steps.

2. The Solution: The "Decision Tree" (The Trie)

VineLM builds a giant decision tree (which the paper calls a "Trie"). Imagine a choose-your-own-adventure book where every page is a step in the investigation.

The Map: Every path through the book represents a different combination of detectives you could hire.
The Annotations: Before you start solving real cases, VineLM runs thousands of practice cases to map out this tree. It marks every path with: "If you go this way, it usually costs $X, takes Y seconds, and gets the right answer Z% of the time."

3. The Magic Trick: "Cascade Profiling" (The Efficient Map-Maker)

Mapping every single path in this giant book would be incredibly expensive and slow (like hiring every detective for every possible scenario). VineLM uses a clever trick called Cascade Profiling:

The Shortcut: Instead of testing every path from scratch, it starts at the beginning. If the first step succeeds, it knows the whole path is a success without needing to test the rest.
The Result: It fills in the map using only 1% to 2% of the effort it would take to test everything. It's like realizing that if you win the first round of a tournament, you don't need to play the final match to know you could have won it; you just need to know the odds.

4. The Runtime: "Re-Rooting" the Tree

This is the most exciting part. When a real request comes in:

Step 1: The system picks the best detective for the first step based on the map.
Step 2: The detective finishes. The system looks at the map again.
The Pivot: The system says, "Okay, we just spent 5 seconds on step 1. We have 10 seconds left. The map says if we go down this branch, we might run out of time. Let's switch to that branch instead."
The Loop: It does this after every single step. It can switch from a "Super Detective" to a "Budget Intern" in the middle of a loop if the situation changes.

Why Does This Matter?

The paper tested this on two types of tasks:

Turning English questions into SQL database queries (NL2SQL): Like asking "What were sales last quarter?" and having the AI write the code to find it.
Math Reasoning: Solving complex math problems that require checking and re-checking the work.

The Results:

Better Accuracy: VineLM got the right answer 18% more often than the old systems, even when using the exact same budget. It's like getting a better grade on a test without paying for extra tutoring.
Cheaper Setup: Because of the "Cascade Profiling" trick, it cost 98–99.8% less to build the map than it would have to test every single possibility.
Fewer Timeouts: If a step took longer than expected, VineLM could instantly switch to a faster plan to stay within the time limit. It reduced "time-out" errors by up to 85%.

The Bottom Line

VineLM treats AI workflows not as a rigid, pre-written script, but as a dynamic journey. It allows the system to make tiny, smart adjustments at every single step, ensuring that you get the best possible result for the least amount of money and time, without getting stuck in a bad plan just because you signed it at the beginning.

Technical Summary: VineLM

Problem Statement

Modern AI applications increasingly rely on agentic workflows, which interleave configurable Large Language Model (LLM) stages with tool stages (e.g., SQL execution, retrieval) and often include refinement loops (retries) to improve output quality. Existing workflow managers, such as Murakkab, employ coarse-grained control. These systems profile full workflow configurations offline and assign each incoming request a static, workflow-level plan. In this paradigm, a specific model is bound to a stage template for the entire duration of a request. Consequently, if a workflow contains a refinement loop, the same model must be reused for every iteration of that loop, regardless of intermediate execution feedback or changing budget constraints.

This static approach limits performance in two critical ways:

Inflexibility in Refinement Loops: The optimal model for an early repair attempt (often a cheaper, faster model) may differ from the optimal model for a later attempt (which may require a stronger model to resolve complex failures). Coarse-grained control cannot mix models across iterations of the same loop.
Lack of Runtime Adaptation: Static plans are based on offline averages. If an early stage invocation consumes more latency or cost than anticipated due to runtime variability, the pre-committed downstream plan may become infeasible (violating SLOs) or suboptimal. Current systems do not reconsider model choices after each stage invocation.

Methodology: VineLM

The authors propose VineLM, a workflow manager that enables fine-grained control by selecting the model for each stage invocation dynamically as execution unfolds.

1. Execution Trie Formulation

VineLM represents the space of feasible executions as an annotated execution trie:

Structure: Each node corresponds to a prefix of model choices encountered so far in a workflow run. Unlike a full tree, the trie respects workflow semantics (e.g., valid transitions, loop bounds).
Shared Prefixes: Nodes represent shared prefixes across many candidate full paths, allowing the system to reason about a large decision space efficiently.
Annotations: Nodes are annotated with estimated metrics: expected cumulative cost ( $\bar{C}$ ), expected cumulative latency ( $\bar{T}$ ), and expected accuracy ( $\bar{A}$ ).

2. Offline Trie Construction (Sparse Profiling)

Fully profiling every request on every path is infeasible due to the combinatorial explosion of paths. VineLM addresses this via a sparse profiling pipeline:

Checkpointing: To avoid re-executing shared prefixes, the system checkpoints the state after common prefixes and reuses them to evaluate different suffixes.
Cascade Sampling: For each sampled request, the system executes a random depth-1 model. If it fails, it proceeds to a depth-2 extension, and so on. This generates "free" labels via subtree fill-in: if a query succeeds at a prefix, all extensions of that prefix are marked successful.
Cascade Decomposition: Standard matrix completion fails here because the observation pattern is Missing Not At Random (MNAR); deeper paths are only observed on requests where earlier stages failed. VineLM uses a cascade decomposition estimator to correct this bias. It treats the observed success rate of a depth- $d$ path as the conditional probability of success given that all previous stages failed, combining this with the unconditional success of earlier stages to estimate the true path accuracy.
Low-Rank Smoothing: To reduce noise in deep paths with few samples, the system applies rank-1 SVD projection to conditional accuracy estimates.

3. Online Model Selection

At runtime, VineLM interleaves execution and control:

Re-rooting: After each stage invocation completes, the controller re-roots the trie at the realized execution prefix.
Dynamic Replanning: The controller searches the remaining subtrie (descendants of the current node) to find the optimal suffix based on the realized latency/cost so far and the remaining budget.
Load Awareness: If load estimates are available, the controller inflates latency estimates for congested backends, steering requests away from paths likely to violate SLOs.
Pruning: The search utilizes the monotonicity of metrics (cost and latency increase, accuracy does not decrease along a path) to prune infeasible or suboptimal branches.

Key Contributions

Demonstration of Coarse-Grained Limitations: The paper shows that binding a single model to a refinement loop leaves significant performance on the table, particularly when mixed-model trajectories are required to satisfy cost/latency constraints while maximizing accuracy.
Trie-Based Formulation: It formulates fine-grained workflow control as a search over an annotated execution trie of workflow prefixes, enabling efficient offline estimation and online adaptation.
VineLM System: The design and implementation of VineLM, which combines the trie formulation with checkpointing, cascade profiling, and dynamic re-rooting to enable per-invocation model selection.
Empirical Validation: Evaluation on NL2SQL and math reasoning workflows demonstrating improvements in the cost-latency-accuracy frontier with minimal profiling overhead.

Results

The paper evaluates VineLM on NL2SQL (with 8 and 2 candidate models) and MathQA (self-reflection) workflows, comparing against Murakkab-style baselines.

Accuracy Improvement: VineLM achieves up to 18% higher accuracy at the same per-request budget compared to coarse workflow-level baselines.
Profiling Efficiency: The sparse profiling approach reduces offline profiling costs by 98–99.8% compared to exhaustive profiling. At a 2% profiling coverage, VineLM's estimator achieves a Mean Absolute Error (MAE) of ~1% in predicting path accuracy, closely matching the performance of a fully profiled trie.
Latency SLO Compliance: Dynamic re-rooting reduces latency-SLO violations by up to 85% compared to static plans, particularly under runtime load variance. Load-aware replanning further reduces violations under high load.
Overhead: The runtime overhead of dynamic replanning is negligible (e.g., 0.592% of the fastest LLM call time for the MathQA workflow).

Significance and Claims

The paper claims that agentic workflows should be controlled via online policies over execution prefixes rather than fixed workflow configurations. By moving from coarse-grained, static assignments to fine-grained, dynamic selection, systems can better navigate the trade-offs between cost, latency, and accuracy in the presence of loops and runtime variability. VineLM demonstrates that this level of control is practical, achieving near-optimal performance with a fraction of the profiling cost required by exhaustive methods. The work suggests that the decision granularity of workflow managers is a critical factor in optimizing agentic systems, and that the "combinatorial explosion" of fine-grained paths can be managed effectively through structured search spaces (tries) and efficient estimation techniques.