Opinion for the court filed by Circuit Judge RANDOLPH.

United States employers wishing to hire alien workers must navigate a maze of statutory provisions and regulations administered by the Immigration and Naturalization Service and the Department of Labor. Samuel G. Kooritzky, an immigration lawyer and a prospective employer of an alien, filed an action to enjoin enforcement of one such regulation on the ground, among others, that the Department of Labor promulgated it without notice. The district court granted summary judgment in favor of the government and Kooritzky brought this appeal.

I

An alien seeking to emigrate from a foreign country to the United States may not legally enter without an immigrant visa issued by the United States Consul in his country. With exceptions not pertinent to this case, immigrant visas are subject to quotas. The- Immigration Act of 1990 established initial annual immigration limits of 465,000 visas for family-sponsored immigrants, 140,000 visas for employment-based immigrants, and 55,000 visas for “diversity” immigrants. Pub.L. No. 101-649, tit. I, § 101(a), 104 Stat. 4978 (1990), codified at 8 U.S.C. § 1151. Two employment-based categories require, as a condition to the alien’s obtaining an immigrant visa, that the alien not only present a petition approved by the Attorney General but also a labor certification issued by the Secretary of Labor. 8 U.S.C. §§ 1153(b)(2) & (3), 1182(a)(5)(A) & (C). ^[1]

[*1511] A labor certification reflects the Secretary’s determination that:

(I) there are not sufficient workers who are able, willing, qualified ... and available at the time of application for a visa and admission to the United States and at the place where the alien is to perform such skilled or unskilled labor, and

(II) the employment of such alien will not adversely affect the wages and working conditions of workers in the United States similarly employed.

8 U.S.C. § 1182(a)(5)(A)(i); see 20 C.F.R. § 656.1(a)(1) & (2). For employers, obtaining a labor certification is the first step toward filling a job with an alien worker. The employer starts by completing an Application for Alien Employment Certification and filing it with the state employment service office. ^[2] On the application, the employer provides the name of the particular alien the employer intends to employ; a description of the alien’s qualifications and the job; and documentation of the employer’s attempts to recruit American workers in compliance with Labor Department regulations. See 20 C.F.R. § 656.21. According to appellant, processing the application may take from two months to two years, as the state agency seeks to determine that no American worker is available for the position.

Within the preference categories, immigrant visas are issued on a first-come-first-served basis. An alien’s place in line is determined by his or her “priority date,” that is, the date when the employer filed the application with the state agency. See 8 C.F.R. § 204.5(d); 22 C.F.R. §§ 42.53(a) & 42.42. When the state agency completes its investigation, the Labor Department reviews its report and the application. If satisfied that the statutory criteria have been met, the Department approves the application and issues the employer an Alien Employment Certification, or as it is commonly known, a labor certification. The certification is “valid indefinitely.” See 20 C.F.R. § 656.30(a).

The employer’s next step is to submit the labor certification and a Petition for Immigrant Worker (Form 1-140) to the Immigration and Naturalization Service. See 8 C.F.R. § 204.5. If the Service approves the petition, it forwards it with the labor certification and the employer’s priority date to the U.S. Consulate in the country from which the alien is being recruited. See id. § 204.-5(n)(l). ^[3] Because of the heavy demand for the limited number of visas in the employment-based preference groups, the alien and his prospective employer often must wait several more years before the visa is issued. In the meantime the alien may become unable or unwilling to take the job. Rather than start all over again, employers naturally prefer to substitute another alien on the labor certification. Before Medellin v. Bustos, 854 F.2d 795 (5th Cir.1988), however, the Labor Department prohibited “the substitution of one alien on a labor certification for another alien if more than six months [had] elapsed since the original date of certification.” Id. at 797. Matters changed as a result of the Fifth Circuit’s decision. Medellin held that the six-month limit on substitutions exceeded the Department’s authority, in part because substituting one alien for another after six months could have no effect on the subject within the Department’s regulatory ambit — the labor market. Thus, as things stood after Medellin, an employer could freely replace the original alien with another and still retain the priority date issued when the employer filed with the state employment agency.

[*1512] In 1991, in the wake of the 1990 Immigration Act’s revisions of the immigration laws, the Department and the Service published separate notices of proposed rulemaking. The Service’s proposed rule, 56 Fed.Reg. 30,703 (July 5, 1991), concerned new immigrant classifications and requirements established in the 1990 legislation. The Service also proposed amending regulations dealing with employment-based preferences so that the priority date would become the date on which the petition for classification of the alien is filed with the Service, rather than the date on which the employer files the application for labor certification with the state agency. See id. at 30,709.

The Labor Department’s proposed rule, 56 Fed,Reg. 32,244 (July 15,1991), in its preamble, indicated that the Department would implement changes wrought by the 1990 Act and would make other technical modifications of its regulations. Id. at 32,245. In response to comments on its Advance Notice of Proposed Rule Making, 56 Fed.Reg. 11,705 (Mar. 20, 1991), and, apparently, in response to the Service’s proposed rulemaking notice, the Department announced that it would not alter its existing rule that labor certifications were valid indefinitely, and that it would work closely with the Service to ensure that the Service’s proposed change in the priority date system would apply only to applications filed after October 1, 1991. 56 Fed.Reg. at 32,246.

On October 23, 1991, the Department promulgated what it called an “interim final rule” containing a significant new provision not mentioned in the notice of proposed rule-making. See 56 Fed.Reg. 54,920 (1991). The new provision amended 20 C.F.R. § 656.30(c)(2) to limit the validity of labor certifications to the alien named on the employer’s application. ^[4] See 56 Fed.Reg. at 54,930. This change eliminated the employer’s freedom to substitute a new alien when the alien named in the application became unable or unwilling to accept the job. An employer in that predicament would have to begin anew; and the alien named in the new application would go to the end of the line for immigrant visas.

The Department gave two explanations for ending substitution. It said first that it reached this decision after consulting the Service about its proposed change in the priority-date system; the Service indicated that if the Department would eliminate substitution, this would “facilitate[ ]” the Service’s retaining its existing method of determining priority dates. 56 Fed.Reg. at 54,-922. ^[5] The Department also wrote that it had abolished substitution because of the “innumerable operational problems” this had caused the Service, including problems associated with a “reputed secondary market involving the sale of labor certifications!!;] the potential for abuse”; unfairness to other aliens not benefiting from substitution and to American workers who might have become available for the job at the time of the substitution; and administrative burdens. 56 Fed. Reg. at 54,922, 54,926.

In announcing the interim final rule and its effective date of November 22, 1991, the Department “reopened” the rulemaking comment period through November 30, 1991. 56 Fed.Reg. at 54,920. The Department received more than a hundred comments but it never responded to them and it has not promulgated a new rule.

II

One of Kooritzky’s contentions, the only one we need consider because we agree with it, is that the Labor Department failed to comply with the notice and comment provisions of the Administrative Procedure Act,[*1513] 5 U.S.C. § 553(b) & (c). Agencies must include in their notice of proposed rulemaking “either the terms or substance of the proposed rule or a description of the subjects and issues involved.” 5 U.S.C. § 553(b)(3). And they must give “interested persons an opportunity to participate in the rulemaking through submission of written data, views, or arguments.” 5 U.S.C. § 553(c). The Labor Department did neither.

The Department’s notice of proposed rulemaking did not contain the terms of the no-substitution rule it later promulgated; it did not propose abolishing substitution; and it did not mention the issues involved in doing so. That is not, however, necessarily fatal. It is an elementary principle of rule-making that a final rule need not match the rule proposed, indeed must not if the record demands a change. See, e.g., Fertilizer Inst. v. EPA, 935 F.2d 1303, 1311 (D.C.Cir.1991); Small Refiner Lead Phase-Down Task Force v. EPA, 705 F.2d 506, 546-47 (D.C.Cir.1983); International Harvester Co. v. Ruckelshaus, 478 F.2d 615, 632 & n. 51 (D.C.Cir.1973). The reason is plain enough. Agencies should be free to adjust or abandon their proposals in light of public comments or internal agency reconsideration without having to start another round of rulemaking. International Harvester, 478 F.2d at 632 n. 51. The necessary predicate, however, is that the agency has alerted interested parties to the possibility of the agency’s adopting a rule different than the one proposed. The adequacy of the notice depends, according to our precedent, on whether the final rule is a “logical outgrowth” of the proposed rule. Fertilizer Inst., 935 F.2d at 1311; see also AFL-CIO v. Donovan, 757 F.2d 330, 338 (D.C.Cir.1985). Because the “logical outgrowth” formulation may be merely another way of asking “how much notice is enough,” Small Refiner, 705 F.2d at 547, answering the question may prove difficult in some cases. This is not one of them.

The Department’s interim final rule does not even come close to complying with the notice requirement of § 553. Something is not a logical outgrowth of nothing. The notice of proposed rulemaking contains nothing, not the merest hint, to suggest that the Department might tighten its existing practice of allowing substitution. Substitution is neither discussed nor mentioned. The subject is not touched upon in any of the rules proposed. Anyone reading those proposals would have assumed that 20 C.F.R. § 656.-30(e) would not be affected. The Department did publish a change it wanted to make in 20 C.F.R. § 656.30, but the suggested amendment merely would have replaced the word “job” with the word “employment” in the phrase “local job service office date stamped” in subsection (b).

The Federal Register Act, 44 U.S.C. §§ 1501-1511, and the regulations thereunder, require agencies to include a preamble to their notice of proposed rulemaking “which will inform the reader, who is not an expert in the subject area, of the basis and purpose for the ... proposal.” 1 C.F.R. § 18.12(a). To the nonexpert reader, the Department’s preamble in July offered no clues of what was to come in October. To experts in the field, the preamble allayed any fears that the Department’s substitution rule was on the table. The preamble stated that the Department had “decided to limit [its] proposed rule to implementing the changes made to the permanent labor certification process by the [1990] Act and to minor technical changes.” 56 Fed.Reg. at 32,245. Yet the final no-substitution rule implemented no changes made by the 1990 Act and it is not by any stretch a “minor technical change.” Furthermore, the notice announced that the proposed rules would not “affect” 20 C.F.R. § 656.30, the section providing that a labor certification is valid indefinitely. 56 Fed. Reg. at 32,246. The interim final rule did more than simply “affect” § 656.30. It prohibited what the rule had permitted. 56 Fed.Reg. at 54,925, 54,930.

The Department’s preamble did mention the Service’s proposed change in its designation of priority dates. But in this respect the Department said only that it would work with the Service “in an effort to insure that[*1514] any new regulations apply only to applications filed after October 1, 1991.” 56 Fed. Reg. at 32,246. No one could have suspected from this brief reference regarding retroac-tivity that the Department not only would work with the Service, but also would lay down its substitution rule as a bargaining chip for the Service’s retaining its existing rule on priority dates. An article in an immigration law journal, published shortly after the Department promulgated its interim final rule, reported that a leading member of the immigration bar approved the trade-off. DOL’s Final Rules IssuedEmployers’ Concerns Allayed, Immig. Pol’y & L., Nov. 1, 1991, at 1. The district court treated this as evidence “that the integral nature of the trade-off between priority dates and substitution was a well-known and much debated issue among the organized immigration bar.” Kooritzky v. Martin, No. 91-3011-LFO, 1992 WL 172572, at *5, 1992 U.S.Dist.LEXIS 9401, at *13-*14 (D.D.C. July 1, 1992). The immigration lawyer submitted an affidavit to the district court stating that he was never “apprised that the regulations governing substitution of aliens in the labor certification process were about to change,” and that he simply intended to indicate that the anti-substitution rule was not a “major blow” to his practice. Apart from the affidavit, we do not believe the article leads to the district court’s conclusion. That some members of the interested public approved of the final rule hardly demonstrates that they and others had reason to anticipate it. If it were proper to look beyond the terms of the Department’s notice of proposed rulemaking, but cf. AFL-CIO v. Donovan, 757 F.2d at 340, far more compelling evidence tells a different story. The Department received more than one hundred comments regarding the interim final rule’s elimination of substitution, each highly critical of the change. The Department had received no comments on the subject in response to its notice of proposed rulemaking.

It may well be, as the district court stated, that the substitution rule and priority dates are interrelated, even though substitution is within the Department’s jurisdiction while priority dates are within the Service’s. But the question is not whether a proposal of one agency is logically related to the proposal of another agency. The Department offered no proposal on substitution despite its awareness of the Service’s intentions. Interested persons, including Kooritzky, therefore had no opportunity to present their views on the matter before the Department acted. The Department gave them no reason to believe substitution would be a subject of its final rulemaking.

We therefore hold that the Department of Labor promulgated its 1991 amendment to 20 C.F.R. § 656.30(c) in violation of 5 U.S.C. § 553. A “reviewing court shall,” the APA instructs, “set aside agency action” when the agency has acted arbitrarily or “without observance of procedure required by law,” 5 U.S.C. § 706(2)(D). See, e.g., American Petroleum Inst. v. EPA, 906 F.2d 729, 742 (D.C.Cir.1990); Advanced Micro Devices v. CAB, 742 F.2d 1520, 1542-43, 1544 (D.C.Cir.1984). The judgment of the district court is therefore reversed and the case is remanded. We leave it to the district court to fashion appropriate relief in accordance with this opinion.

So Ordered.