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:
- Free-form JSON: Fast, but the LLM often hallucinates invalid syntax or incorrect identifiers.
- 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").
- 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.
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.
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