#Introduction
During my internship at AWS, I was tasked with rewriting an internal headcount summary service. The service lived inside a TypeScript monolith originally meant to be a proxy111Some thin layer of logic that lives in between the headcount app and all headcount services. for every other service related to internal headcounts. Due to sacrificing code quality and maintainability for shipping speed, that proxy grew to include more and more business logic, becoming increasingly difficult to maintain. My project was to move this headcount summary service into a standalone Java Lambda for better performance and scalability.
Because this service returns data that drives hiring and organizational structure decisions, the rewrite needed to maintain response parity with the legacy service. That is, I needed to figure out how to take the many permutations (magnitudes of ~millions!) of filters we can apply to this headcount service and minimize it to ensure with some confidence that its able to be shipped to production.
I figured that, not only can I do a rewrite, I can automate it, and create some type of framework for agents to write and test the code to maintain response parity. This framework could support future migrations not only for services in this proxy, but also for services outside the FinTech org! In this post, I'll walkthrough intuition on how we can create a testing framework to ensure data parity given many parameters with exponentially growing permutations and how we can create an automatic code review loop for agents to recursively test, improve, and iterate!
#Models struggle with sparse dependencies
We first need to figure out what bugs we should look out for. That is, besides minor alignment issues, why do we even need testing with frontier models?
Research (old models) and my own testing (Opus 5, Fable 5, GPT-5.6 Sol) suggest that agents struggle to trace behavior across sparse dependencies.222When Liljas and colleagues had GPT-4o and Llama 4 agents map out open-source microservice systems, the connections between services were the hardest part to recover. The agents tended to leave them out rather than invent them.333Rarity makes it worse. In CloudAPIBench, GPT-4o made valid calls to common AWS and Azure APIs over of the time, and to rare ones less than of the time. Another team's internal service is as rare as an API gets, since it appears in no public code at all. Even giving agents specific skills and context to look and grep the repositories of the services it depends on, agents still struggled to trace behavior and intended architecture needed to rewrite this service. At AWS, the headcount service relied on services owned by other teams with little documentation available to the agent. That left it to infer and hallucinate conventions like ID formats and date boundaries from their use in the legacy code. This is especially problematic when conventions are not standardized across the services and are decided arbitrarily by the teams.
Illustrative example of sparse dependencies
For example, the headcount service can send a bare cost center code 1234 to a dependency that expects the code with a prefix CC-1234
(it should be standardized, but sometimes at large companies that's not possible).
Both are valid strings, thus satisfies the type signature, and the call returns an empty page instead of an error.444This is also why unit tests with mocked dependencies won't catch it. The mock answers the way the agent assumed the dependency would, so the test and the code share the same mistake.
These gaps in understanding make service boundaries a useful place to look for bugs! We can use this knowledge to have agents narrow the investigation down to functions that have dependencies.
#Pairwise testing
We then need to figure out what queries we need to test.
A query to the headcount service sets many parameters, such as scope, headcount_type, and measure.
Testing every possible permutation of parameters would grow exponentially!
We can make use of Pairwise testing to test in pairs of parameters instead of every possible permutation.
It chooses queries so that every pair of parameters, such as cost_center with contingent, appears together in at least one query.555Also called all-pairs testing. It's the strength- case of combinatorial testing. Strength would cover every triple of values, at the cost of a much larger test set.
Intuitively, bugs rarely depend on every parameter in a given query.666A study of real failures at NIST found that most were triggered by one or two parameters, and none needed more than six.
Take the prefix bug from the previous section.
A query calls the contingent workforce system only when it asks for contractors, with headcount_type=contingent.
It sends that system a cost center code only when it counts a cost center, with scope=cost_center.
Those parameters, regardless of the other parameters, will always trigger the bug.
Pairs also narrow down where to look. The previous section showed that bugs gather at dependency boundaries, and a pair of settings often decides which dependency a query calls and what the call carries. So when a failure traces back to cost_center × contingent,
the agent can narrow down the search to one place!
Testing pairs instead of combinations also shrinks the test set size, and it shrinks further because one query covers many pairs at once. Take a query with parameters, each with values. Testing every combination takes queries. Pairwise testing only has to cover every pair of values: the parameters form pairs of parameters, and each of those has value pairs, for pairs in total. If each query tested one pair, that would still take queries. But a query sets all parameters, so it covers one value pair for each of the parameter pairs at the same time. That means at least queries are needed, and well-chosen queries are enough to cover all pairs, against for every combination!777 is also the fewest possible here. For two-valued parameters the minimum is known exactly, and queries can cover every pair of at most parameters. With more values per parameter there's no known fast way to find the minimum, which is why PairDiff builds its test set greedily.
Every permutation we can query
Every pair
cost_center × managerOrg directorycursor pagingAcost_center × prior_yearCost center ledgereffective-datedBopen_req × prior_yearHR recordsstatus codesBcost_center × contingentContingent workforce"CC-" prefixed codesAquarter_end × fiscalFiscal calendarinclusive end datesA#PairDiff
Now that we know what bugs to look out for and what queries need to be tested, it's time to put together a framework! We can have an agent code the service, then give it the ability to check for bugs with PairDiff. If bugs are found, PairDiff feeds the discrepancies and associated context back into the agent for it to iterate and fix these bugs until parity is achieved.
PairDiff works in three steps:
- Build a cohesive test set that covers every pair.
- Send each query in the test set to both the legacy and the new service, and diff the two responses.
- Report every difference to the coding agent, which fixes the new service and runs the test set again.
Architecture diagram of PairDiff v1
#Building the test set
Before we can build our test set, there's one catch.
Some parameters can take far too many values to pair directly. For example, as_of can be any date.
So we group those dates by how the legacy code handles them. We can call each group a value class.888Aka equivalence partitioning.
For example, quarter_end can take an extremely large range of dates. However, note that we
only care about functionality and applicability of this date. We know that if one date works properly all would
as it would exercise the same date-handling logic.
So instead of pairing headcount_type=contingent with every quarter-end date, we pair it with quarter_end once.
A query for contractors on any quarter-end date covers that pair.
Parameters with only a few options, like headcount_type, don't need grouping, so each option is its own class.
From here on, a pair means two value classes from different parameters, like as_of=quarter_end with headcount_type=contingent.
Some combinations aren't valid queries at all. So PairDiff also keeps a list of constraints, and it covers only the pairs that the constraints allow.
Now, which queries go in the test set? Live traffic is the best place to start. Intuitively, we want to fix bugs that users are more likely to come across.
PairDiff builds the test set one query at a time. It keeps track of which pairs are still open, meaning no query in the test set holds them yet. Remember that one query holds many pairs at once. So at each step, PairDiff looks through the distinct queries in a recent window of the request log and counts the open pairs each one holds. That count is the query's gain. The query with the highest gain goes into the test set, and its pairs are no longer open. This is called greedy set cover.999Greedy isn't optimal, but it's provably close. For pairs, it never uses more than about times the fewest possible queries, and no fast algorithm can do much better unless P = NP.
Eventually, no logged query holds an open pair.
The pairs still open are combinations nobody sent, which are also the ones a rewrite is least likely to get right by accident!
For each of them, PairDiff builds a synthetic query.
It can't scan every possible query the way it scans the log, because the number of possible queries grows exponentially with the parameters.
Instead, Synthesize starts from one open pair and fills in the other parameters one at a time, each with the value that gives the most gain.101010This is the strategy of AETG, one of the first pairwise testing tools. IPOG works the other way around: it covers the pairs among the first few parameters, then adds one parameter at a time, and extends to triples and beyond. Starting from an open pair suits PairDiff, which only has to fill the gaps that live traffic left.
Add the query with the most open pairs until no pair is open. It comes from the log while a logged query still helps, and from Synthesize after that.
Build Algorithm on a small log.
#Comparing legacy and the new service
Next, we need to send each query from our test set into the legacy service and our new one and diff them.
The problem is that we can't guarantee that the two calls happen at the same time and query the same data. It's possible that the headcount database changes in the very small that is between the legacy and new service queries.
To combat this, we can use a very simple approach of querying both services twice.
This rule assumes that a correct rewrite disagrees with legacy only when data changes between the two calls. When working on alpha or beta data (basically static), there is probabilistically low chance of data changing between this small , so with some very high degree of confidence, we can assume that is true.
Of course, if we wanted to test with a production database, this assumption doesn't always hold, we'll come back to it in Improvement 1.
#Reporting failures to the agent
Finally, we can then feed each failing query with context back into the coding agent.
A failing query on its own tells the agent only that something is wrong. So the report also names a pair, which points the agent at the dependency call behind the failure.
Let's go back to the prefix bug from the sparse dependencies section. Because of the missing prefix, the contingent workforce system returns an empty page. So for a cost center with contractors, legacy counts them and the new service counts none:
{
"pair": { "headcount_type": "contingent", "scope": "cost_center" },
"query": { "scope": "cost_center", "id": "4471", "headcount_type": "contingent",
"as_of": "2026-03-31", "group_by": "none", … },
"legacy": { "total": 1452, "counts": { "regular": 1240, "contingent": 212 } },
"candidate": { "total": 1240, "counts": { "regular": 1240, "contingent": 0 } },
"diff": [
{ "path": "$.total", "legacy": 1452, "candidate": 1240 },
{ "path": "$.counts.contingent", "legacy": 212, "candidate": 0 }
]
}
Example of discrepancy report
#Iterative Features
Note that we can append additional features and bits of context to help out the agents as well. We can do some type of iterative learning, where upon every bug and fix the agent applies, ask it what additional information would be helpful for finding and fixing this bug?
Take the prefix bug again. Once it's fixed, the agent might say it needed two things, an example:
| The agent says it needed | What PairDiff does with it |
|---|---|
| The request each service sent to the contingent workforce system | Puts both services' dependency calls in every report |
| To know that this system expects cost center codes with a "CC-" prefix | Writes it down in a notes file that every later agent reads |
Over many fixes, the reports and the notes grow with whatever the agents found missing. They can also bloat, and every extra field is one more thing for the agent to read. So we also ask the agent which parts of the report it actually used, and drop the features that later agents keep ignoring.
Example of PairDiff adding features after the prefix bug is fixed.
Note that adding a feature changes PairDiff itself, so it needs the same check as any other change to PairDiff, which we cover next.
#PairDiff can recursively repair itself
So far, we've assumed that PairDiff is right and the new service is wrong. But not every discrepancy is a bug in the new service. Some come from PairDiff itself, such as a diff that compares numbers too strictly, or a missing constraint.
From our research, when agents get the discrepancy report along with context on PairDiff (its code, and design docs like this post), they can discern which discrepancies are bugs in the new service and which come from PairDiff itself. So they can fix bugs in PairDiff too!
Example of PairDiff repairing itself.
We can have a second agent, a review agent, verify that PairDiff has properly been modified. This prevents situations where an agent will modify PairDiff falsely to circumvent testing.111111When a check fails, weakening the check is often the easiest way to make it pass. This is a form of reward hacking, and a separate reviewer makes it much harder to get away with.
Example of the review agent rejecting an agent trying to circumvent testing.
#Improving PairDiff
I think with modern models and in pursuit of shipping fast, v1 is good enough. Fundamentally, all we needed was some high probability way of verifying that the new service had response parity with the old one and a way for agents to properly implement and iterate on it.
However, upon reflecting on PairDiff, I think there are some obvious improvements we can make:
#Improvement 1: Record dependencies and data
Recall that the two-round comparison assumes data rarely changes between the two calls. If querying a production database, that doesn't hold.
We can instead send every dependency call of both services through a proxy that records and replays them.121212The catch is that a replay only works for calls the new service makes the same way legacy did. A call with no matching recording is worth flagging on its own, since it means the two services talk to the dependency differently. Improvement 2 builds on that.
Example of recording legacy's calls and replaying them to the new service.
#Improvement 2: Diff the dependency calls
Going back to what the agent asked for after fixing the prefix bug in Recursive Features: the request each service sent to the contingent workforce system. With Improvement 1, we can track and diff dependency calls for extra context.
Example of a call diff. Legacy sends the cost center code with a "CC-" prefix and the new service sends it without, so the new service's call comes back empty.
Of course, a different call isn't a bug on its own. An optimized rewrite may batch or page its calls differently. However, given this additional context, it can tell the agent where to look.
{
"signature": "$.counts.contingent lower",
"cluster": { "failing": "<queries with the symptom>", "without_symptom": "<queries without it>" },
"localized": {
"pair": { "scope": "cost_center", "headcount_type": "contingent" },
"evidence": "the only shared pair with no alibi; every confirming query fails"
},
"repro": { "request": "requests/<query>.json", "recording": "recordings/<query>/" },
"response_diff": [ { "path": "$.counts.contingent", "legacy": 212, "new": 0 } ],
"call_diff": [ {
"dependency": "contingent-workforce", "op": "listWorkers",
"legacy": { "costCenter": "CC-4471", "records": 212 },
"new": { "costCenter": "4471", "records": 0 }
} ]
}
Example of discrepancy report v2
#Future Work (Formal Verification)
In the age of software engineering work being offloaded to agents and recursively hillclimbed131313As shown via PairDiff!, verifying that the code the agents wrote is correct is more important than ever. I think Jane Street puts it best here.
TLDR: Formal methods can help in two ways: they make review more efficient, and they give agents stronger feedback, which agents thrive on. Tests, property-based testing and fuzzing still matter, but tests can only sample a program's state space. Type systems give universal guarantees, such as eliminating all data races, or making XSS impossible, or ensuring 100% data parity!
Transitioning this service is fairly low risk141414This is an internal tool, where we roll out the new service slowly to a small group of testers. and fairly low engineering work151515This is loosely a micro-service part of a larger service.. I think for larger rewrites - or fundamentally, for more complete and larger rewrites - formal verification will be important and standard with how we write software with agents!
#Footnotes
-
Some thin layer of logic that lives in between the headcount app and all headcount services. ↩
-
When Liljas and colleagues had GPT-4o and Llama 4 agents map out open-source microservice systems, the connections between services were the hardest part to recover. The agents tended to leave them out rather than invent them. ↩
-
Rarity makes it worse. In CloudAPIBench, GPT-4o made valid calls to common AWS and Azure APIs over of the time, and to rare ones less than of the time. Another team's internal service is as rare as an API gets, since it appears in no public code at all. ↩
-
This is also why unit tests with mocked dependencies won't catch it. The mock answers the way the agent assumed the dependency would, so the test and the code share the same mistake. ↩
-
Also called all-pairs testing. It's the strength- case of combinatorial testing. Strength would cover every triple of values, at the cost of a much larger test set. ↩
-
A study of real failures at NIST found that most were triggered by one or two parameters, and none needed more than six. ↩
-
is also the fewest possible here. For two-valued parameters the minimum is known exactly, and queries can cover every pair of at most parameters. With more values per parameter there's no known fast way to find the minimum, which is why PairDiff builds its test set greedily. ↩
-
Greedy isn't optimal, but it's provably close. For pairs, it never uses more than about times the fewest possible queries, and no fast algorithm can do much better unless P = NP. ↩
-
This is the strategy of AETG, one of the first pairwise testing tools. IPOG works the other way around: it covers the pairs among the first few parameters, then adds one parameter at a time, and extends to triples and beyond. Starting from an open pair suits PairDiff, which only has to fill the gaps that live traffic left. ↩
-
When a check fails, weakening the check is often the easiest way to make it pass. This is a form of reward hacking, and a separate reviewer makes it much harder to get away with. ↩
-
The catch is that a replay only works for calls the new service makes the same way legacy did. A call with no matching recording is worth flagging on its own, since it means the two services talk to the dependency differently. Improvement 2 builds on that. ↩
-
As shown via PairDiff! ↩
-
This is an internal tool, where we roll out the new service slowly to a small group of testers. ↩
-
This is loosely a micro-service part of a larger service. ↩