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

Nikos Pagonas, Matthew Lou, Tianyi Peng, Dan Rubenstein, Kostis KaffesarXiv 2026 · arXiv

TL;DR

VineLM is a novel workflow manager for LLM agents that enables fine-grained, step-by-step model selection during execution rather than relying on static, upfront plans. By modeling execution paths as an annotated trie and using smart sparse profiling, VineLM delivers up to 18% higher accuracy under strict cost or latency constraints while slashing offline profiling costs by up to 99.8%.

What Problem Does This Paper Address?

Modern AI applications increasingly rely on "agentic workflows"—complex pipelines that interleave LLM generations with tool usage, retries, and self-correction loops. Managing these workflows requires choosing which LLM to route to at each stage, balancing cost, latency, and accuracy.

Current state-of-the-art workflow managers use coarse-grained control. They profile configurations offline and bind a single model to a specific stage template before the request even starts. For example, if a workflow includes a "Repair" loop, the manager forces every single iteration of that loop to use the exact same model.

This leaves significant performance on the table for two reasons:

  1. No Mixed-Model Strategies: It prevents starting with a cheap model for easy fixes and escalating to a more powerful, expensive model only if early attempts fail.
  2. Inability to Adapt to Runtime Variance: LLM latencies fluctuate wildly based on prompt lengths and server loads. A static plan cannot pivot to a faster model downstream if an early step runs unexpectedly long, leading to missed Service Level Objectives (SLOs).
Comparing coarse-grained workflow managers to VineLM's per-invocation fine-grained control.

Methods

VineLM shifts the paradigm to fine-grained control, treating every single stage invocation as an independent decision point. It achieves this through three core components:

  • The Execution Trie: VineLM maps out all feasible execution paths as a trie. Each node represents a specific prefix of model choices, annotated with its expected cumulative cost, latency, and accuracy.
  • Sparse Cascade Profiling: Exhaustively profiling every request on every path suffers from combinatorial explosion. VineLM samples paths in a "cascade" order (only executing deeper steps if previous ones fail) and leverages subtree fill-in (if a step succeeds, all its descendants are marked as successful for free). To fix the inherent sampling bias—where deeper paths are only tested on harder queries—VineLM introduces a mathematical correction called Cascade Decomposition paired with low-rank SVD smoothing.
  • Dynamic Re-rooting: At runtime, VineLM does not commit to a fixed path. After each stage invocation completes, the controller shifts ("re-roots") the trie to the newly realized prefix, updates the remaining budget based on actual elapsed time and cost, and runs a pruned Depth-First Search to select the optimal model for the very next step.
Figure 2. For a specific NL2SQL request, the objective is to return the correct answer under a fixed cost SLO. Static single-model plans fail in opposite ways: always using GLM 4.7 reaches the correct answer but exceeds the budget, while always using Gemma 27B or always using Qwen 32B stays within budget but returns the wrong answer. A mixed path— GLM 4.7 for generation, then Gemma 27B and Qwen 32B on successive repair rounds—stays within the SLO and returns the correct answer. This illustrates why refinement loops should be optimized as a sequence of model choices, not by binding one model to the entire loop.

Datasets

The authors evaluated VineLM across two popular, refinement-heavy agentic workflow patterns:

  • NL2SQL (Natural Language to SQL): A pipeline that generates a SQL query, executes it, and enters a bounded repair loop if errors occur. It was tested in two flavors: NL2SQL-8 (8 candidate models, max depth 3) and NL2SQL-2 (2 candidate models, max depth 4).
  • MathQA: A self-reflective math question-answering workflow allowing up to 6 sequential reflection iterations across 4 candidate models.

The model pool included a wide array of commercial and open-source models, such as Claude 3.5 Sonnet, Gemma-3-27B, Qwen3-32B, GLM-4.7, Llama-3.3-70B, and DeepSeek-V3.2.

Key Insights and Ideas

  • Loops are Sequences, Not Blocks: The core "aha moment" is that optimization should happen at the level of individual loop iterations. Conditioning the value of a repair step on the exact history of previous failures allows the system to price continuations much more accurately.
  • Exploiting Problem Structure to Defeat Bias: While cascade profiling creates heavily biased data (Missing Not At Random), the prefix-closed nature of workflows means the data contains its own bias correction. By estimating incremental conditional accuracies rather than absolute path accuracies, VineLM bypasses the need for expensive, full matrix completion.
  • Asymmetric Metric Handling: Cost budgets can be safely optimized using expected averages. Latency budgets, however, are strict per-request constraints. VineLM handles this by avoiding early-stopping discounts on downstream latency estimates, ensuring robust real-time guarantees.
Figure 4. Illustrative execution trie with two configurable stages and two admissible models per stage. Each node 𝑝 is annotated with expected cumulative cost ¯𝐶(𝑝), expected cumulative latency ¯𝑇(𝑝), and expected accuracy ¯𝐴(𝑝) if exe- cution terminated at that prefix. All three metrics are mono- tone along each root-to-leaf path.

Key Results

  • Superior Pareto Frontiers: VineLM consistently beats coarse-grained baselines, achieving up to 18% higher accuracy under identical cost budgets.
  • Drastic Profiling Cost Reductions: Thanks to cascade profiling and checkpoint reuse, VineLM cuts offline profiling costs by 98% to 99.8% (a 47× to 535× savings) compared to exhaustive profiling.
  • Fewer SLO Violations: By dynamically adjusting to actual execution times and server queueing delays, VineLM reduces latency SLO violations by up to 85% under heavy artificial loads.
  • Negligible Runtime Overhead: Re-rooting and searching the trie takes mere microseconds (e.g., 33 𝜇s for NL2SQL-2), accounting for less than 1% of the latency of the fastest LLM call.

Limitations and Future Work

  • Context Prefill Overhead: Switching models mid-loop means the system cannot fully reuse KV caches, requiring a full context re-prefill. While VineLM measures and factors this overhead into its trie annotations, it remains a physical bottleneck.
  • Fixed Workflow Topologies: VineLM assumes a predefined workflow template. Extending this fine-grained control to fully autonomous, open-ended agents with dynamic graph structures remains an open challenge.
  • Joint Hardware Allocation: The authors note that combining VineLM's model routing with infrastructure-level decisions (like dynamic replica selection or hardware provisioning) is a promising direction for future research.

Summary updated

Abstract

Agentic workflows interleave configurable LLM stages with tool stages and often include retries or refinement loops. Existing workflow managers profile full workflow configurations offline and assign each request a static workflow-level plan that binds each configurable LLM stage to a single model, reuses that model across repeated loop iterations, and does not revisit those choices at runtime. We present VineLM, a workflow manager that enables fine-grained control by choosing the model for each stage invocation as execution unfolds under request-level objectives such as maximizing accuracy under cost or latency budgets. VineLM represents feasible executions as an annotated trie of model-choice prefixes and uses checkpointing and cascade profiling to estimate path accuracy, cost, and latency without exhaustively profiling every request on every path. At runtime, VineLM re-roots the trie after each stage invocation and replans over the remaining subtrie using the realized execution prefix and remaining latency budget. On NL2SQL and math reasoning workflows, VineLM improves the cost-latency-accuracy frontier over coarse workflow-level baselines, achieving up to 18% higher accuracy at the same per-request budget with its sparse profiling reducing offline profiling cost by 98-99.8% when compared to exhaustive profiling.
BibTeX
@misc{pagonas2026vinelm,
  author = {Nikos Pagonas and Matthew Lou and Tianyi Peng and Dan Rubenstein and Kostis Kaffes},
  title = {{VineLM: Trie-Based Fine-Grained Control for Agentic Workflows}},
  year = {2026},
  eprint = {2605.23914},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2605.23914},
}

Loading related content...

Figure