Compiling Autoregressive LLM Control into Policy-Exact Parallel Inference for Hierarchical RAG

Zehao Lin, Qianfeng Shen, Xixuan Hao, Shaobo Cui, Chunyu Li, Kai Chen, Bo Tang, Zhenjun Wang, Jin Yan, Zhiyu Li, Feiyu XiongarXiv 2026 · arXiv

TL;DR

LLMs are increasingly used as "controllers" to navigate complex document structures in Hierarchical RAG, but they are held back by the slow, serial nature of text decoding. This paper introduces a method to "compile" these structured decisions into a parallel inference task, reducing control latency by up to 47% while remaining mathematically equivalent to traditional serial decoding.

What Problem Does This Paper Address?

In Hierarchical Retrieval-Augmented Generation (RAG), an LLM acts as a navigator, repeatedly choosing which sections of a massive document tree to explore. Currently, developers face a "three-way dilemma" when implementing this:

  1. Free-form JSON: Fast, but the LLM often hallucinates invalid syntax or incorrect identifiers.
  2. Grammar-Constrained Decoding: Reliable and context-aware, but painfully slow because it requires a separate forward pass for every single token and piece of punctuation (the "serial critical path").
  3. The Unary Shortcut: Fast (one pass to score all options), but it ignores the "memory" of the controller—the LLM can't base its second choice on what it picked first.

The authors argue that this dilemma is an artifact of how we execute LLMs, not a limitation of the models themselves.

Methods

The core innovation is Finite-Action Control Compilation. Instead of decoding tokens one by one, the authors map out the "reachable future" of the decision process as a shallow prefix tree.

  • Action-Prefix Tree: Since the LLM is only choosing a small number of items (e.g., picking the top 3 out of 20 sections), the total number of possible states is finite and relatively small.
  • Tree-Causal Probe: Instead of multiple serial passes, the system performs one "root prefill" and one "tree-causal probe." This probe uses a specialized block-causal mask that allows the LLM to evaluate every possible decision path in parallel. Each "branch" in the probe sees exactly the tokens, positions, and history it would have seen during serial decoding.
  • Policy Exactness: The authors prove a "prefix-state lemma," showing that in exact arithmetic, the logits produced by this parallel probe are identical to those from serial decoding.
Fig. 1. Compile, don’t decode. (a) Serial grammar decoding spends one dependent forward per emitted token (b+msyn ≈9). (b) Compilation: one root prefill, then a single tree-causal probe evaluates the trunk and every candidate branch under a block-causal mask — each row sees only the cached prompt and its own ancestors, so its logits equal the serial controller’s in exact arithmetic (Lemma 1). (c) Fresh split D, 7B: mean control latency −36%, zero output tokens and protocol failures; fp32 replay (split A): mean graph deviation ≈0.05.

Datasets

The researchers evaluated their approach using:

  • QASPER: A dataset for question answering over scientific papers, which provides a natural hierarchy (sections, subsections, paragraphs).
  • Fresh Splits: They used five distinct splits (A-E), including a preregistered fresh split (E) to ensure the results weren't overfitted to specific documents.
  • Synthetic Sweeps: To test how the method scales with different "frontier widths" (number of candidates) and "horizons" (number of items to select).

Key Insights and Ideas

  • Trading Depth for Width: The method essentially exchanges "serial depth" (waiting for one token to finish before starting the next) for "parallel width" (calculating many possibilities at once). This is a massive win on modern GPUs, which have high parallel throughput.
  • Serialization is Optional: For bounded-horizon tasks (like tool use or routing), we don't actually need to "generate" text. We just need to probe the model's preferences across a known set of actions.
  • History Dependence is Pervasive: The authors found that the "unary shortcut" (ignoring previous choices) significantly degrades quality. LLM decisions are highly interdependent; what the model picks second depends heavily on what it picked first.
  • Precision Matters: While the method is mathematically exact, real-world hardware uses floating-point math (like bf16). Small "near-tie" differences in how numbers are rounded can occasionally cause the compiled version to pick a different path than the serial version, but these are rare and usually involve choices the model was "unsure" about anyway.

Key Results

  • Speed: Compiled control cut latency by 35–47% compared to standard serial decoding. It even beat an "idealized chunked engine" (a theoretical baseline that fast-forwards through syntax) by 6–7%.
  • Fidelity: The compiled policy matched the serial policy on 84–89% of questions. Nearly all divergences were identified as floating-point near-ties.
  • Reliability: The system achieved zero protocol failures (no broken JSON) and required zero output tokens to be generated, as the decisions are read directly from the logits.
Fig. 2. Work–depth scaling at the deployed frontier (k=20, 7B, synthetic): serial grammar decoding, the idealized chunked engine (D=n; it overlaps compiled here, while Sec. 4.1 separates them on real workloads), and compiled control (D=2); the dotted b=4 probe shows the measured break-even of Eq. (3). The 3B model repro- duces the pattern.

Limitations and Future Work

  • The "Width Wall": The number of rows in the parallel probe grows factorially with the number of items being selected. While it works beautifully for selecting 3 or 4 items, selecting 10+ items would require too much memory and compute, making serial or "staged" execution more efficient.
  • Hardware Specificity: Because the results are sensitive to floating-point rounding, a "parity dial" (replaying near-ties serially) is required for applications that demand bit-for-bit identity with serial decoding, though this comes at a performance cost.
  • Future Directions: The authors suggest this compilation technique could be applied to other finite-action agent loops, such as tool selection, routing, or agenda management.

Summary updated

Abstract

Large language models increasingly act as controllers in structured decision pipelines, yet their decisions are still executed by autoregressive text decoding. Hierarchical RAG is one such setting: at each frontier of a document tree, an LLM commits to $b$ of $k$ sections under an input-dependent action grammar, executed as either failure-prone free-form JSON or reliable but strictly serial grammar-constrained generation. We show that this serialization is unnecessary for bounded-horizon control: the reachable future forms a shallow action-prefix tree, which we compile --- one root prefill plus one tree-causal probe evaluate every prefix-conditioned action distribution with serial decoding's tokens, positions, and causal ancestry. A prefix-state lemma makes compiled control policy-exact in exact arithmetic: the same policy with a two-forward critical path and zero output tokens. One further probe pass certifies the exact order-marginalized MAP set. Across four document-disjoint splits and two scales on the primary MetaX device, compiled control matches the serial policy on $84$--$89\%$ of questions --- every instrumented divergence a floating-point near-tie --- and cuts control latency by $35$--$47\%$ versus token-wise serial decoding and $6$--$7\%$ versus an idealized chunked engine; an H800 repetition preserves the ordering.
BibTeX
@misc{lin2026compiling,
  author = {Zehao Lin and Qianfeng Shen and Xixuan Hao and Shaobo Cui and Chunyu Li and Kai Chen and Bo Tang and Zhenjun Wang and Jin Yan and Zhiyu Li and Feiyu Xiong},
  title = {{Compiling Autoregressive LLM Control into Policy-Exact Parallel Inference for Hierarchical RAG}},
  year = {2026},
  eprint = {2610.30664},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.30664},
}
Figure