Many future quantum technologies rely on the generation of entangled states. Quantum devices will require verification of their operation below some error threshold, but the reliable detection of quantum entanglement remains a considerable challenge for large-scale quantum systems. Well-established techniques for this task rely on the measurement of expectation values of entanglement witnesses, which however require many measurements settings to be extracted. Here we develop a generic framework for efficient entanglement detection that translates any entanglement witness into a resource-efficient probabilistic scheme, whose confidence grows exponentially with the number of individual detection events, namely copies of the quantum state. To benchmark our findings, we experimentally verify the presence of entanglement in a photonic six-qubit cluster state generated using three single-photon sources operating at telecommunication wavelengths. We find that the presence of entanglement can be certified with at least 99:74% confidence by detecting 20 copies of the quantum state. Additionally, we show that genuine six-qubit entanglement is verified with at least 99% confidence by using 112 copies of the state. Our protocol can be carried out with a remarkably low number of copies and in the presence of experimental imperfections, making it a practical and applicable method to verify large-scale quantum devices.