McLAUGHLIN, Circuit Judge:

Defendant-appellant Louis W. Sullivan, M.D., the Secretary of the United States Department of Health and Human Services (the "Secretary"), appeals from a judgment entered in the United States District Court for the Southern District of New York (Pierre N. Leval, Judge), granting judgment on the pleadings in favor of plaintiffs-appellees Cesar A. Perales, Robert Abrams, and the New York State Department of Social Services (collectively "the State" or "New York").

This action arises out of the State's request for federal reimbursement under the Medicaid statute, 42 U.S.C. § 1396 et seq., of medical assistance payments the State had made to various persons who were later found disabled. The Secretary denied the State's request, asserting that the State had failed to make individual determinations of disability before filing its claim for federal reimbursement. The Grant Appeals Board ("GAB") of Health and Human Services ("HHS") upheld the Secretary's decision, reasoning that when the State filed its claim for reimbursement, there was no "assurance" that documentation existed to prove that the persons receiving State funds were actually disabled.

The State challenged the ruling of the GAB in the district court. Both the State and the Secretary subsequently moved for judgment on the pleadings. The district court granted the State's motion and overturned the GAB's decision, finding that the GAB's unexpected imposition of a requirement of assurance of documentation was arbitrary and capricious. We agree with the district court and, therefore, affirm.

BACKGROUND

1. The Medicaid Act and Regulations

Title XIX of the Social Security Act, 42 U.S.C. § 1396 et seq. (the "Medicaid Act" or the "Act") establishes a cooperative federal and state program for medical care of indigent persons. Under the Medicaid Act, states reimburse health care providers for their costs in treating low income and disabled patients who are unable to pay for health care. If the state's reimbursement plan meets federal regulations, the state may, in turn, receive reimbursement of its expenses from the federal government.

To qualify for federal reimbursement, a state's plan must meet a host of statutory and regulatory requirements. See 42 U.S.C. § 1396a, 42 C.F.R. § 431 et seq. Among HHS regulations is a requirement that a state seeking federal reimbursement maintain individual records on each recipient of state funds. The records must include information as to the recipient's eligibility to participate in the state's program, as well as statistical, fiscal, and other data. See 42 C.F.R. § 431.17(b).

After "qualification" comes the actual distribution of federal reimbursement. Not surprisingly, this involves yet another myriad of statutory and regulatory guidance. Before the beginning of each quarter, a state that wants federal reimbursement must submit a report to the Secretary estimating how much the state's Medicaid-eligible expenses will be in the upcoming quarter. See 42 U.S.C. § 1396(d)(1). The Secretary then pays that state a preliminary amount based on this estimate. Id. § 1396b(d)(2). At the end of the quarter, the state submits a quarterly expense report ("QER") to the Secretary. The QER is the state's actual claim for reimbursement. HHS regulations define a QER as:

[A]n accounting statement of the disposition of the Federal funds granted for past periods [which] provides the basis for making the adjustments necessary when the State's estimate for any prior quarter was greater or less than the amount the State actually expended in that quarter.

45 C.F.R. § 201.5(a)(3)

The QER does not contain any case-specific or recipient-specific information. Rather, it summarizes the state's actual quarterly expenditures that are eligible for federal reimbursement. Under HHS practice, a state may submit a QER by simply completing HHS form HCFA-64, specifying the federal reimbursement the state requests and the dates the state incurred the expenses. No other documentation must be attached to this form.

If the Secretary believes the state's claim for federal reimbursement is of "questionable allowability," he may, within sixty days, defer reimbursement of the claim. 45 C.F.R. § 201.15(c)(1). If he does, HHS regulations require him to demand that the state "make available for inspection all documents and materials . . . necessary to determine the allowability of the claim." 45 C.F.R. § 201.15(c)(2). He must make this demand within fifteen days of the deferral. The state must then give the documentation to the Secretary within sixty days, or request a sixty-day extension to do so. If the Secretary ultimately finds the documentation unsatisfactory, he is required to "promptly notify the State," which must then respond within fifteen days. If the documentation remains insufficient after the state's response, the Secretary "shall promptly disallow the claim." 45 C.F.R. § 201.15(c)(5).

Many states, including New York, also have separate programs furnishing health care to people in financial difficulty who are not eligible for Medicaid. Although the Medicaid Act does not prohibit such programs, monies spent by states in these programs are not automatically eligible for federal reimbursement. An individual receiving funds under a state program, however, may later be classified by the state as eligible for Medicaid, and if this happens, the state may submit a claim for federal reimbursement of the funds it expended for the now Medicaid-eligible person. Requests for reimbursement of these state funds are also submitted in a QER.

The states used to be able to file a QER seeking federal reimbursement for monies spent under state programs, regardless of how many years had elapsed since the state actually made payment to a health care provider. This bureaucratic nightmare was eliminated in 1980 when Congress imposed a two-year limitation upon the states to make a claim for reimbursement. The limitation is codified in 42 U.S.C. § 1320b-2:

[A]ny claim by a State for payment with respect to an expenditure made during any calendar quarter by the State . . . shall be filed (in such form and manner as the Secretary shall by regulations prescribe) within the two-year period which begins on the first day of the calendar quarter immediately following such calendar quarter; and payment shall not be made under this chapter on account of any such expenditure if claim therefor is not made within such two-year period . . . .

Id. (emphasis added). Under HHS regulations, the two-year limitation begins to run when the state pays a health care provider for an individual's medical care. See 45 C.F.R. § 95.13(b).

2. New York's Medical Assistance Programs

New York's federally approved Medicaid program provides medical assistance to three categories of people. First, New York provides for the "categorically needy," defined as those who receive benefits under Aid to Families with Dependent Children ("AFDC") and individuals receiving Supplementary Security Income ("SSI") Second, New York provides medical assistance to those who qualify for AFDC or SSI, but for some reason do not receive such benefits. Finally, New York supplies medical assistance to individuals who do not qualify for either AFDC or SSI, but who have extremely high medical expenses.

As noted earlier, New York also maintains its own medical assistance programs that do not automatically qualify for federal reimbursement under the Medicaid Act. One such program known as "Home Relief" provides funds for medical care to individuals whose income and resources are below a certain level determined by the state, but who are still ineligible to receive SSI or AFDC. Many people receive aid from New York under the Home Relief program. Some of these people are later found disabled, and thus eligible for SSI and Medicaid. However, due to the sheer number of people who are eventually determined to be disabled, New York has found itself unable to complete individualized determinations of disability for each person within the two-year statutory limitation of 42 U.S.C. § 1320b-2.

Rather than risk the loss of federal reimbursement while making an individualized determination of disability for each person, New York developed a statistical technique (from July 1982 until December 1984) by which the State selected a sample of cases where it made payments under Home Relief. The State then determined the percentage of cases where the recipient later became sufficiently "disabled" to qualify for Medicaid. The State calculated its total claim by applying this percentage to the total number of cases in which it made medical payments under Home Relief without HHS reimbursement, and included this figure in each of ten QERs filed from July 1982 to December 1984.

HHS was dissatisfied with this method of calculating federal reimbursement, and issued deferral notices and requests for further documentation. Discussions ensued between State officials and HHS concerning the State's claims and the State's statistical methods. During these negotiations, the State went back and made actual disability determinations for several thousand cases that had previously been part of the statistical extrapolation submitted to HHS. The State then submitted these findings to HHS.

In a letter dated March 9, 1985, the Secretary notified the State that he would not allow nearly $163 million of the State's claim for federal reimbursement. The Secretary took issue with the State's failure to make a determination of disability for each individual before filing its claim. He concluded that the State's method of statistical extrapolation violated HHS regulations regarding reimbursement.

New York appealed the Secretary's decision to the GAB, and on November 4, 1986, the GAB issued a draft decision proposing to reverse the Secretary's decision. The GAB draft stated that the Medicaid Act, while requiring timely filing of a claim for reimbursement, did not require timely documentation of the claim. In any event, the GAB noted that the necessary documentation was available to the Secretary; he needed merely to collect the documentation from the State.

The GAB invited both the State and the Secretary to comment on the draft decision. The Secretary responded, arguing that the State had to actually possess documentation of disability for each individual when it filed its QER. Since relevant information to determine disability was physically located at hospitals and other health care facilities, and not in a State office, the Secretary argued that the State did not have adequate evidence of a patient's disability at the time it filed its claim.

The GAB eventually withdrew the draft decision, and, agreeing with the Secretary, found that the State had to collect from the files of health care providers the documentation required for a finding of disability. That documentation existed outside state offices was irrelevant, said the GAB, as the state would have to "piece together" these documents to determine disability. Thus, the GAB held that because there was no "assurance" at the time of filing the claim for reimbursement that documentation of disability really existed, the State had not made a valid claim. See New York State Dep't of Social Services, GAB Decision No. 854 at 10 (March 31, 1987) ("Decision No. 854").

New York appealed the GAB's decision to the United States District Court for the Southern District of New York, arguing that the GAB's decision was arbitrary and capricious as well as an abuse of discretion. Both sides cross-moved for judgment on the pleadings. The district court granted New York's motion for judgment on the pleadings, holding that the "assurance" requirement of the GAB's decision had no statutory or regulatory foundation, and, accordingly, was arbitrary and capricious. The district court remanded the case to HHS for further administrative proceedings. The Secretary now challenges the district court's decision to remand.

DISCUSSION

1. Appealability

There is a threshold issue — not noted by either party — as to whether the district court's decision to remand is an appealable order. Because this question affects our jurisdiction we cannot avert our gaze, but must raise the issue of appealability on our own motion. See Bender v. Clark, 744 F.2d 1424, 1426 (10th Cir. 1984).

28 U.S.C. § 1291 gives a court of appeals jurisdiction of appeals from all "final decisions" of a district court. To be final, a decision must generally end the litigation on the merits, leaving nothing for the court to do except execute the judgment. Firestone Tire Rubber Co. v. Risjord, 449 U.S. 368, 373, 101 S.Ct. 669, 672-73, 66 L.Ed.2d 571 (1981). A district court's remand to an administrative agency, however, keeps a case alive and hence is ordinarily not appealable. See Lyons v. Barrett, 851 F.2d 406, 409 (D.C.Cir. 1988); Daviess County Hosp. v. Bowen, 811 F.2d 338, 341 (7th Cir. 1987). An exception to the finality requirement is recognized when the agency to which the case is remanded seeks to appeal, and that agency would be unable to appeal after the proceedings on remand. Occidental Petroleum Corp. v. SEC, 873 F.2d 325, 330 (D.C.Cir. 1989).

The exception applies here. The district court's remand puts the case back in the hands of the Secretary, who then has two options. He can either grant New York's request for reimbursement, or he can deny the request in whole or in part. Regardless of which option he selects, the Secretary will not appeal his own order. See Sullivan v. Finkelstein, ___ U.S. ___, 110 S.Ct. 2658, 2664, 110 L.Ed.2d 563 (1990). The district court's decision to remand the case to the Secretary is therefore "final" as to him for the purpose of 28 U.S.C. § 1291, since the district court's decision to remand precludes any appeal by the Secretary. Thus, we have jurisdiction.

2. Standard of Review

The district court heard no testimony. It reviewed the GAB's decision solely on the basis of the administrative record compiled throughout the lengthy process initiated by the State's filing of its claim for reimbursement. The district court made no factual findings. We therefore engage in a de novo review of the district court's decision. See Vallejo Gen. Hosp. v. Bowen, 851 F.2d 229, 230-31 (9th Cir. 1988); Daviess County Hosp., 811 F.2d at 342-43.

Under the Administrative Procedure Act, 5 U.S.C. § 706(2)(A), a court shall:

[H]old unlawful and set aside agency actions, findings, and conclusions found to be arbitrary, capricious, an abuse of discretion, or otherwise not in accordance with law. . . .

Id. Thus, an agency's interpretation of a statute will be accepted by a reviewing court unless the agency's interpretation is "arbitrary, capricious, or manifestly contrary to the statute." Chevron U.S.A. Inc. v. Natural Resources Defense Council, Inc., 467 U.S. 837, 844, 104 S.Ct. 2778, 2782, 81 L.Ed.2d 694 (1984). While a court may not substitute its own judgment for that of the agency, it must still determine whether the agency's decision was based on a consideration of all relevant factors and whether the agency made a clear error of judgment. Citizens to Preserve Overton Park, Inc. v. Volpe, 401 U.S. 402, 416, 91 S.Ct. 814, 823-24, 28 L.Ed.2d 136 (1971). Even though the scope of review is narrow, a reviewing court must carefully probe into the agency's actions. Blassingame v. Secretary of Navy, 866 F.2d 556, 559 (2d Cir. 1989). Our inquiry, therefore, must focus on whether the GAB's decision that New York failed to provide assurance that the State possessed the necessary documentation to support a determination of each individual's disability was arbitrary and capricious.

An agency's action is arbitrary and capricious when it fails to meet statutory, procedural, or constitutional requirements. Motor Vehicle Mfrs. Ass'n. v. Ruckelshaus, 719 F.2d 1159, 1164 (D.C.Cir. 1983). While an agency may adopt new regulations when necessary to achieve its statutory mandate, it is a basic requirement of the Administrative Procedure Act that notice of any proposed substantive regulation must be given to those subject to the regulation. See 5 U.S.C. § 553. Notice can come from a variety of sources, including Congress, the enactment process itself, and prior agency decisions. Regardless of its form, however, notice is the sine qua non of enactment of a substantive regulation.

A "substantive regulation" is one which "grant[s] rights, impose[s] obligations, or produce[s] other significant effects on private interests." Batterton v. Marshall, 648 F.2d 694, 701-02 (D.C.Cir. 1980). Such a regulation may be compared with an "interpretative" regulation, which is simply an agency's "intended course of action, its tentative view of the meaning of a particular statutory term, or internal house-keeping measures organizing agency activities," and does not require notice prior to its enactment. Id. at 702.

There can be no question that the assurance requirement was a substantive regulation. It precluded what would otherwise have been a valid claim for federal reimbursement. Thus, HHS was required to give notice to New York prior to enacting the assurance requirement.

The Secretary does not contest that his agency's rule requiring documentary assurance is indeed substantive. However, he makes several arguments that New York had adequate notice of the assurance requirement.

The Secretary contends that the assurance requirement actually lightens the burden New York must bear in proving its claim for reimbursement. He argues that the State had notice of the assurance requirement since the requirement is merely part of a regulation that had already been validly promulgated. He directs us to 42 C.F.R. § 435.541, which he contends mandates that a state seeking federal reimbursement must have a completed medical report and social history proving an individual's disability before the State files its claim for reimbursement. Thus, he concludes, the assurance requirement dilutes the regulation by demanding merely the state's assurance that documentation exists to support a disability finding, rather than requiring the state to have prepared the actual disability report. This argument is more ingenious than ingenuous because it rests upon a misinterpretation of 42 C.F.R. § 435.541.

Under 42 C.F.R. § 435.541(e), a state must obtain a "medical report and other non-medical evidence for individuals applying for Medicaid on the basis of disability." Nothing in 42 C.F.R. § 435.541, however, addresses when a state must obtain this information. The GAB decision imports into the regulation language that is not there: a requirement that the documentation assurance exist when the claim is filed. See Decision No. 854 at 17. The assurance requirement imposes the additional obligation that the State maintain a record keeping system which assures the availability of the documents at the time the State files its claim for reimbursement. We must reject the Secretary's argument that the assurance requirement is already mandated by previously promulgated regulations.

The Secretary maintains, in the alternative, that the assurance requirement is just a logical extension of various sections of the Medicaid Act and accompanying regulations, as well as previous GAB decisions. More specifically, he directs our attention to 42 U.S.C. § 1396b(a)(1), detailing the process of distributing federal reimbursement, and 42 U.S.C. § 1320b-2, imposing the two-year limitation on filing reimbursement claims. The Secretary also points us to 45 C.F.R. § 201.5, which prescribes the form and manner of the State's claim for federal reimbursement. Finally, he relies on two prior decisions of the GAB addressing the methodology a state must employ when estimating its claim for reimbursement. Our analysis of these various references does not support the Secretary's conclusion.

A. 42 U.S.C. § 1396b(a)(1)

Section 1396b(a)(1) directs the Secretary to distribute federal reimbursement for the total "amount expended . . . as medical assistance under the State plan." This section makes reimbursable only those medical expenditures made by a state in accordance with the state's Medicaid plan. Since federal regulations require that a state Medicaid plan include a medical report and social history for all persons receiving Medicaid-eligible funds, see 42 C.F.R. § 435.541(e), the Secretary asserts that a state reclassifying its medical expenses as eligible for Medicaid reimbursement must also meet this federal standard. The Secretary argues that the assurance requirement merely ensures that state expenses reclassified as eligible for federal reimbursement follow the same standard for reimbursement as funds originally expended under the state's Medicaid plan. Certainly, this is a sensible argument. Without such a rule, a state could simply avoid the federal standards by treating all medical expenditures as reclassified claims, rather than originally eligible claims. However, the issue is not whether the assurance requirement is sensible, but rather whether New York had notice of the requirement. Our examination of Section 1396b(a)(1) shows that it did not.

For the purpose of the Medicaid Act, an expense is incurred when a state pays a health care provider. See 45 C.F.R. § 95.13(b). An expense, then, is simply the spending of funds. Expenses are not, as the Secretary argues, the spending of funds plus the subsequent reclassification of those funds as eligible for Medicaid reimbursement. The reclassification of funds as Medicaid-eligible is not embraced within the concept of the "amount expended . . . as medical assistance under the state plan." The reclassification procedure, accordingly, need not follow regulations promulgated under Section 1396b(a)(1), and the assurance requirement cannot be justified under that section.

The Secretary's argument also ignores a prior decision of the GAB construing another section of the Medicaid Act. In New York State Dep't of Social Services, GAB Decision No. 521 (March 6, 1984) ("Decision No. 521"), the GAB held that an "expenditure" for the purposes of 42 U.S.C. § 1320b-2 is made when a medical provider is paid, not when the state later reclassifies its expenses as eligible for federal reimbursement. Id. at 11. The Secretary argues now that an expenditure also occurs when a state reclassifies the money it has paid as Medicaid eligible. In effect, the Secretary asks us to interpret similar statutory language in a contradictory manner. Similar language in two different sections of the same law should be given a similar interpretation. Northcross v. Board of Education, 412 U.S. 427, 428, 93 S.Ct. 2201, 2202, 37 L.Ed.2d 48 (1973) ( per curiam); Director, Office of Workers' Compensation Programs, U.S. Dep't. of Labor v. Goudy, 777 F.2d 1122, 1127 (6th Cir. 1985); Yamaguchi v. State Farm Mut. Auto. Ins. Co., 706 F.2d 940, 947 (9th Cir. 1983). The GAB has already determined the meaning of the word "expenditure." We hold that a claim for reimbursement of prior medical expenses is no more an "expenditure" under Section 1396b(a)(1) than it was under Section 1320b-2, and is therefore not subject to the record-keeping requirements of Section 1396b(a)(1).

B. 42 U.S.C. § 1302b-2

42 U.S.C. § 1320b-2 provides that any state claim for reimbursement shall be filed within two years of the state's payment to a health care provider, and it must be "in such form and manner as the Secretary shall by regulations prescribe." We interpret a statute in accordance with the ordinary meaning of the language contained within the statute. Absent a clearly expressed Congressional intention to the contrary, we regard the statutory language as conclusive. Consumer Product Safety Comm'n. v. GTE Sylvania, Inc., 447 U.S. 102, 108, 100 S.Ct. 2051, 2056, 64 L.Ed.2d 766 (1980).

The Secretary argues that the assurance requirement is essential for Section 1320b-2 to serve its intended purpose of making expenditures under the Medicaid Act more predictable. See 125 Cong.Rec. S15128 (1979). That may well be, but the Secretary's argument ignores the root question whether the assurance requirement was validly promulgated under Section 1320b-2. Because we find that the Secretary did not follow the required procedure for enacting a substantive regulation to implement Section 1320b-2, we hold that the assurance requirement cannot be justified under Section 1320b-2.

The statutory mandate "shall be regulation" found in Section 1320b-2 instructs the Secretary how to implement the statute: he must validly promulgate regulations governing the form and manner of claims for reimbursement. Cf. Patchogue Nursing Center v. Bowen, 797 F.2d 1137, 1143 (2d Cir. 1986), cert. denied, 479 U.S. 1030, 107 S.Ct. 873, 93 L.Ed.2d 828 (1987) ("By choosing the word `may,' rather than `shall,' `must,' or other mandatory language, Congress allowed the Secretary to exercise discretion in deciding whether regulations were needed to effectuate the statute."). The Secretary may not impose ad hoc conditions on how a state is to file its claim for federal reimbursement. The procedure specified in Section 1320b-2 ensures that states will have sufficient prior notice of any new filing requirements.

The Secretary did not follow the procedure required by Section 1320b-2. We have scoured the regulations promulgated under that section and find no regulation that speaks of an assurance requirement. Indeed, the assurance requirement was created only after the GAB gave the Secretary a chance to "comment" on the GAB's draft decision. Even the draft decision made no mention of an assurance requirement. The Secretary did not consider promulgating an assurance requirement until the GAB withdrew its draft decision. In short, the assurance requirement took New York completely by surprise. We find, therefore, that the assurance requirement was not properly promulgated under Section 1320b-2, however necessary it may be to effectuate the purposes of that section.

C. 45 C.F.R. § 201.5(a)(3)

45 C.F.R. § 201.5(a)(3) prescribes the form and manner in which a state must submit its claim for federal reimbursement. Under this regulation, each state seeking reimbursement must present its claim in a "quarterly statement of expenditures" (the QER) that is an "accounting statement of the disposition of the Federal funds granted for past periods." The Secretary argues that since the QER is an accounting statement, it must be based upon complete and individualized documentation of the entire amount of federal reimbursement claimed by the state. In the Secretary's eyes, Section 201.5(a)(3) means that the QER may seek only the amount of federal reimbursement that is substantiated by the state's own records. The assurance requirement thus ensures that the necessary documentation exists to substantiate the QER.

This reading of Section 201.5(a)(3) strains the language of the regulation, which simply requires a state seeking federal reimbursement to submit a QER to the Secretary. A QER accounts for the federal funds previously granted to the state under the Medicaid Act. Nowhere in Section 201.5(a)(3) is there any requirement that the state submit documentation supporting the QER. The regulation provides only that the QER must contain figures from which the Secretary may make adjustments. Indeed, the QER itself is a completed version of HHS form HCFA-64. This form requires a state to list just the amount of federal reimbursement requested and the dates of the quarter in which the state incurred the listed expenditures.

If the Secretary wishes to obtain documentation to support a state's claim, he may use the deferral process. See 45 C.F.R. § 201.15(c). As previously noted, the procedure for filing a claim for reimbursement, according to HHS regulations, begins with a state submitting its claim for reimbursement on form HCFA-64. The Secretary may then defer payment of the claim and request additional documentation, and he may disallow the claim if adequate documentation is not furnished within the prescribed time period.

There is nothing in Section 201.5(a)(3) obligating the State to provide an assurance that documentation of disability exists before the Secretary makes a request for the documentation. Thus, we find that the GAB acted arbitrarily and capriciously in relying on Section 201.5(a)(3) as authority for the assurance requirement.

D. Prior GAB Decisions

The Secretary's final contention is that two prior GAB decisions, New York State Dep't of Social Services, GAB Decision No. 537 (May 30, 1984) ("Decision No. 537") and New York State Dep't of Social Services, GAB Decision No. 542 (June 4, 1984) ("Decision No. 542") support the assurance requirement. A careful examination of these decisions, however, proves otherwise.

In Decision No. 537, New York submitted a QER estimating the amount of federal reimbursement to which it was entitled. The Secretary denied the State's claim, and the State appealed to the GAB. The GAB reversed the Secretary, holding that a QER need not contain an exact calculation of the State's entitlement to federal reimbursement. Rather, the state need only submit a "figure which is as definite as reasonably possible under the circumstances." Decision No. 537 at 15. Moreover, the GAB held that HHS regulations did not require "an instantly available compilation" of the documentation supporting the QER. Since the State's estimates in Decision No. 537 were based on a computerized audit and review of available documentation and ancillary sources, the GAB held that the State had made a valid claim for federal reimbursement.

In Decision No. 542, the State submitted an estimated claim for federal reimbursement that was based solely on the "experience and knowledge" of a State employee. The GAB disallowed the State's claim for federal reimbursement, holding that the State "must at least know where the documentation for the claim is" and it could not submit a figure that was "little more than an outright guess."

Neither Decision No. 537 nor Decision No. 542 supports the Secretary's argument. Both decisions focused on the State's use of estimated figures on the QER. As the GAB stated: "[T]he real question is where did the figure [on the QER] come from?" Decision No. 542 at 7 (quoting Decision No. 537 at 15). In this case, by contrast, there is no doubt where the figures on the QER came from. The State explained that the figures on the QER were an extrapolation from a sample of cases that the State had determined were eligible for Medicaid reimbursement.

It should not go unnoted that the Secretary has never questioned the validity of the State's estimate in this case. Rather, the issue in this case is the documentation a state must possess when filing its QER. This issue was not addressed by the GAB in either Decision No. 537 or Decision No. 542. The assurance requirement, therefore, cannot emanate from either of these decisions.

CONCLUSION

We find that the district court correctly held that the assurance requirement was arbitrary and capricious. We recognize that courts owe substantial deference to agency construction of a complex statute, and we intend no retreat from our recent statement that "[d]eference [to an Agency's decision] is especially appropriate when reviewing an executive agency's interpretation of a statute as unwieldy as the Medicaid Act." New York by Perales v. Sullivan, 894 F.2d 20, 24 (2d Cir. 1990). Nonetheless, an appropriate sense of deference does not require us to condone agency action that took New York by surprise. Our holding today is narrow and is based on the Secretary's creation of a new and unforeseeable rule requiring an "assurance" that documentation of disability exists at the time a state files its claim for federal reimbursement.

We conclude by observing that our holding does not prevent HHS from properly promulgating a rule imposing an "assurance" requirement on states applying for federal reimbursement. Indeed, we recognize that such a rule may be necessary to assist HHS in carrying out its congressional mandate to administer the Medicaid program. Our decision today is essentially a reaffirmation of the well-settled rule that an administrative agency must give prior notice of its intention to enact substantive regulations.

Accordingly, the judgment of the district court is affirmed.