# A Multi-Agent Approach for REST API Testing with Semantic Graphs and LLM-Driven Inputs arXiv: https://arxiv.org/abs/2411.07098 ยท HTML: https://mlsanity.com/paper/2411.07098/ ## Key facts - Cited by 9 papers in the map (data through 14 Oct 2026). - Placed in Software engineering coding agents, one of 16 directions in LLM agents and tool use. - Builds on 24 of its 73 references that are in the map. - First posted on arXiv 11 Nov 2024. ## Placed in - LLM agents and tool use / [Software engineering coding agents](https://mlsanity.com/agents/software-engineering-coding-agents/) ## Builds on (most cited first, 24 of 24) - [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020) - [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023) - [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024) - [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019) - [Value-Decomposition Networks For Cooperative Multi-Agent Learning](https://mlsanity.com/paper/1706.05296/) (2017) - [Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving](https://mlsanity.com/paper/1610.03295/) (2016) - [A Survey and Critique of Multiagent Deep Reinforcement Learning](https://mlsanity.com/paper/1810.05587/) (2018) - [RestGPT: Connecting Large Language Models with Real-World RESTful APIs](https://mlsanity.com/paper/2306.06624/) (2023) - [NESTFUL: A Benchmark for Evaluating LLMs on Nested Sequences of API Calls](https://mlsanity.com/paper/2409.03797/) (2024) - [Leveraging Large Language Models to Improve REST API Testing](https://mlsanity.com/paper/2312.00894/) (2023) - [Automatic Web Testing using Curiosity-Driven Reinforcement Learning](https://mlsanity.com/paper/2103.06018/) (2021) - [Automated Test Generation for REST APIs: No Time to Rest Yet](https://mlsanity.com/paper/2204.08348/) (2022) - [Morest: Model-based RESTful API Testing with Execution Feedback](https://mlsanity.com/paper/2204.12148/) (2022) - [Testing RESTful APIs: A Survey](https://mlsanity.com/paper/2212.14604/) (2022) - [DeepREST: Automated Test Case Generation for REST APIs Exploiting Deep Reinforcement Learning](https://mlsanity.com/paper/2408.08594/) (2024) - [Adaptive REST API Testing with Reinforcement Learning](https://mlsanity.com/paper/2309.04583/) (2023) - [KAT: Dependency-aware Automated API Testing with Large Language Models](https://mlsanity.com/paper/2407.10227/) (2024) - [Open Problems in Fuzzing RESTful APIs: A Comparison of Tools](https://mlsanity.com/paper/2205.05325/) (2022) - [QuickREST: Property-based Test Generation of OpenAPI-Described RESTful APIs](https://mlsanity.com/paper/1912.09686/) (2019) - [Deriving Semantics-Aware Fuzzers from Web API Schemas](https://mlsanity.com/paper/2112.10328/) (2021) - [Automatic Property-based Testing of GraphQL APIs](https://mlsanity.com/paper/2012.07380/) (2020) - [Importance Sampling based Exploration in Q Learning](https://mlsanity.com/paper/2107.00602/) (2021) - [Automated Black-box Testing of Mass Assignment Vulnerabilities in RESTful APIs](https://mlsanity.com/paper/2301.01261/) (2023) - [Improving Program Debloating with 1-DU Chain Minimality](https://mlsanity.com/paper/2402.00276/) (2024) ## Built on by (most cited first, 9 of 9) - [From REST to MCP: An Empirical Study of API Wrapping and Automated Server Generation for LLM Agents](https://mlsanity.com/paper/2507.16044/) (2025) - [LogiAgent: Automated Logical Testing for REST Systems with LLM-Based Multi-Agents](https://mlsanity.com/paper/2503.15079/) (2025) - [CodeAssistBench (CAB): Dataset & Benchmarking for Multi-turn Chat-Based Code Assistance](https://mlsanity.com/paper/2507.10646/) (2025) - [LlamaRestTest: Effective REST API Testing with Small Language Models](https://mlsanity.com/paper/2501.08598/) (2025) - [AutoRestTest: A Tool for Automated REST API Testing Using LLMs and MARL](https://mlsanity.com/paper/2501.08600/) (2025) - [Evaluating LLMs on Sequential API Call Through Automated Test Generation](https://mlsanity.com/paper/2507.09481/) (2025) - [Reproducible, Explainable, and Effective Evaluations of Agentic AI for Software Engineering](https://mlsanity.com/paper/2604.01437/) (2026) - [FlowScout: From Execution Feedback to Reliable Tool-Using Agent Workflows](https://mlsanity.com/paper/2608.10039/) (2026) - [MASTEST: A LLM-Based Multi-Agent System For RESTful API Tests](https://mlsanity.com/paper/2511.18038/) (2025) ## Abstract (arXiv) As modern web services increasingly rely on REST APIs, their thorough testing has become crucial. Furthermore, the advent of REST API documentation languages, such as the OpenAPI Specification, has led to the emergence of many black-box REST API testing tools. However, these tools often focus on individual test elements in isolation (e.g., APIs, parameters, values), resulting in lower coverage and less effectiveness in fault detection. To address these limitations, we present AutoRestTest, the first black-box tool to adopt a dependency-embedded multi-agent approach for REST API testing that integrates multi-agent reinforcement learning (MARL) with a semantic property dependency graph (SPDG) and Large Language Models (LLMs). Our approach treats REST API testing as a separable problem, where four agents -- API, dependency, parameter, and value agents -- collaborate to optimize API exploration. LLMs handle domain-specific value generation, the SPDG model simplifies the search space for dependencies using a similarity score between API operations, and MARL dynamically optimizes the agents' behavior. Our evaluation of AutoRestTest on 12 real-world REST services shows that it outperforms the four leading black-box REST API testing tools, including those assisted by RESTGPT (which generates realistic test inputs using LLMs), in terms of code coverage, operation coverage, and fault detection. Notably, AutoRestTest is the only tool able to trigger an internal server error in the Spotify service. Our ablation study illustrates that each component of AutoRestTest -- the SPDG, the LLM, and the agent-learning mechanism -- contributes to its overall effectiveness.