The news follows an NAO report last week that found the Ministry of Defence was struggling to cut the costs of its vast estate because it lacked centralised data.
The £35 billion target was set by the former Labour government in 2007, as part of the Comprehensive Spending Review.
The NAO investigated five large departments due to deliver £2.8 billion of the savings. It found that while 38 per cent of individual savings targets were sustainable, 44 per cent were uncertain, and 18 per cent "significantly overstate" realistic savings potential.
Problems include a lack of centralised data, difficulties demonstrating links between savings and performance, unsuitable baselines for measurement, and a lack of transparency over reporting.
This was "partly the result of measurement weaknesses, with many departments not having the robust data systems needed to substantiate improvements in value for money", the NAO noted.
Departments needed to improve their financial systems in particular "so that they can identify unit cost of activities, and identify better proxies for current performanc" in areas where the measures used for their key objectives are subject to uncertainty or long delays".
"Public confidence in reported savings is undermined where they do not stand up to external scrutiny," warned Amyas Morse, head of the NAO. "The proportion that does not fully meet the Comprehensive Spending Review criteria is evidence both that the programme was not well enough understood across government and that quality control within departments was not good enough."
A quarter of the savings so far came from process reorganisation. But only a tenth came from the Operational Efficiency Programme with IT and back office changes accounting for four percent. The OEP is aiming to make £7.2 billion savings. Departments needed to think "more radically" about how to reduce costs and sustain this over time, he said.
Upon coming to power in May, the Conservative-Liberal Democrat coalition vowed to vowed to cut 25 per cent from most departments' costs, with reductions in staff, IT systems, consultants and property, as well as process reorganisation, expected to lead the way. Details, expected to include a heavy toll on large IT programmes, will be announced in October's spending review.