FAST MULTI-SCALE GENERALIZATION BOUNDS FOR TOOL-AUGMENTED REASONING IN LARGE LANGUAGE MODELS UNDER HEAVY-TAILED LOSS REGIMES
Keywords:
Index Terms— Heavy-tailed learning, multi-scale generalization bounds, Bernstein condition, Tool-augmented reasoning, Large Language Models (LLMs), Statistical learning theory, Robust estimation.Abstract
The rise of tool-augmented language models (TaLMs) presents a significant challenge for generalization theory, as their error distributions are often heavy-tailed and unbounded, rendering conventional theoretical analyses ineffective. This work establishes fast learning rates for tool-augmented reasoning, which we model as a multi-step process. To control the model's excess risk, we introduce two key structural conditions. First, we assume that the worst-case loss across the hypothesis class possesses a finite moment of order greater than two, ensuring control over extreme deviations. Second, we posit a Multi-Scale Bernstein Condition that links the variance of the error to its expectation across different levels of semantic complexity, characterized by a stability parameter. By leveraging advanced methods from the theory of unbounded empirical processes, we prove that the excess risk converges at a rate that interpolates between the slow and fast classical rates. This rate improves as the loss tails become lighter and the reasoning process becomes more stable. Furthermore, we derive a complexity-aware bound where the required sample size scales favorably with the depth of the reasoning chain, providing a foundational framework for verifying the reliability of neuro-symbolic AI agents.
