# VAKRA: Evaluating Multi-Hop Reasoning Across APIs and Retrieval Under Tool-Use Policies

arXiv: https://arxiv.org/abs/2608.12282 · HTML: https://mlsanity.com/paper/2608.12282/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning.
- Builds on 19 of its 49 references that are in the map.
- First posted on arXiv 12 Aug 2026.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)

## Builds on (most cited first, 19 of 19)

- [WebArena: A Realistic Web Environment for Building Autonomous Agents](https://mlsanity.com/paper/2307.13854/) (2023)
- [ToolLLM: Facilitating Large Language Models to Master 16000+ Real-world APIs](https://mlsanity.com/paper/2307.16789/) (2023)
- [gpt-oss-120b & gpt-oss-20b Model Card](https://mlsanity.com/paper/2508.10925/) (2025)
- [API-Bank: A Comprehensive Benchmark for Tool-Augmented LLMs](https://mlsanity.com/paper/2304.08244/) (2023)
- [From Crowdsourced Data to High-Quality Benchmarks: Arena-Hard and BenchBuilder Pipeline](https://mlsanity.com/paper/2406.11939/) (2024)
- [ToolACE: Winning the Points of LLM Function Calling](https://mlsanity.com/paper/2409.00920/) (2024)
- [RestGPT: Connecting Large Language Models with Real-World RESTful APIs](https://mlsanity.com/paper/2306.06624/) (2023)
- [On the Tool Manipulation Capability of Open-source Large Language Models](https://mlsanity.com/paper/2305.16504/) (2023)
- [MCP-Bench: Benchmarking Tool-Using LLM Agents with Complex Real-World Tasks via MCP Servers](https://mlsanity.com/paper/2508.20453/) (2025)
- [CRAG -- Comprehensive RAG Benchmark](https://mlsanity.com/paper/2406.04744/) (2024)
- [NESTFUL: A Benchmark for Evaluating LLMs on Nested Sequences of API Calls](https://mlsanity.com/paper/2409.03797/) (2024)
- [SOPBench: Evaluating Language Agents at Following Standard Operating Procedures and Constraints](https://mlsanity.com/paper/2503.08669/) (2025)
- [Examining Reasoning LLMs-as-Judges in Non-Verifiable LLM Post-Training](https://mlsanity.com/paper/2603.12246/) (2026)
- [Multi-Document Grounded Multi-Turn Synthetic Dialog Generation](https://mlsanity.com/paper/2409.11500/) (2024)
- [AGENT-CQ: Automatic Generation and Evaluation of Clarifying Questions for Conversational Search with LLMs](https://mlsanity.com/paper/2410.19692/) (2024)
- [Automated Creation and Enrichment Framework for Improved Invocation of Enterprise APIs as Tools](https://mlsanity.com/paper/2509.11626/) (2025)
- [NesTools: A Dataset for Evaluating Nested Tool Learning Abilities of Large Language Models](https://mlsanity.com/paper/2410.11805/) (2024)
- [A New Query Expansion Approach via Agent-Mediated Dialogic Inquiry](https://mlsanity.com/paper/2502.08557/) (2025)
- [Gecko: A Simulation Environment with Stateful Feedback for Refining Agent Tool Calls](https://mlsanity.com/paper/2602.19218/) (2026)

## Abstract (arXiv)

Agents deployed in enterprise settings must reason across structured APIs and document collections, yet existing benchmarks evaluate these capabilities in isolation. We introduce VAKRA (eValuating API and Knowledge Retrieval Agents), a benchmark of over 8,000 executable APIs across 62 domains with tasks spanning three settings of increasing difficulty: diverse API interaction styles, multi-hop reasoning over structured APIs, and multi-source reasoning with natural-language tool-use policy constraints. Correctness is verified by re-executing predicted tool calls against live APIs, accommodating multiple valid paths. Using a fixed ReAct harness to isolate model capabilities from agent architecture, we evaluate frontier and open-weight models and find that even the best model achieves only 70.4% on single-hop endpoint-style tasks and drops to 50--51% on compositional APIs; performance degrades by over 50% as reasoning depth increases, and policy-constrained questions expose severe failures (as low as 2.4% on unanswerable queries). Trace analysis shows failures concentrate at language-mediated reasoning - entity disambiguation, cross-source grounding, rather than tool invocation mechanics. Code is available https://github.com/IBM/VAKRA. Dataset is available https://huggingface.co/datasets/ibm-research/VAKRA