Informed Recursion: Structural Awareness for Recursive Language Agents

Recursive Language Models allow language models to undertake context lengths beyond their designed context windows by treating long prompts as external environments and recursively querying themselves. However, a closer look at this performance reveals a large drop in accuracy on tasks requiring exact numerical counts relative to comparison and existential tasks. We trace this gap to a failure mode in which ordinary classification errors near ambiguous category boundaries are amplified by exact-count and combinatorial aggregation. We introduce Informed Recursion, a single-trajectory approach with two lightweight mechanisms: Query-Structure Routing, which selects recursion depth based on the structure of the query, and Targeted Verification, which re-checks intermediate decisions that can affect the final aggregation. Across our evaluations, Informed Recursion improves RLM performance by adapting recursion depth to query structure and selectively verifying intermediate decisions. Doing so avoids the cost of applying deeper recursion or multiple trajectories to every query. Our analysis indicates that many RLM failures arise from local classification errors that become amplified when their outputs are aggregated, rather than from incomplete access to the context.