dissenting from the order rejecting the suggestion for rehearing en banc.

It is “unlawful for any citizen of the United States to depart from or enter, or attempt to depart from or enter, the United States unless he bears a valid United States passport.” 8 U.S.C § 1185(b). The requirement that someone living in the United States must, before departure, obtain a document establishing his right to reenter applies not just to citizens but to aliens as well. Id. § 1181. 1 The Attorney General is authorized to waive this requirement-as she has with respect to citizens visiting Canada and Mexico by car-but no other circuit has impugned the Attorney General’s authority to impose reasonable administrative requirements, such as the obtaining of reentry authorization, as a condition for leaving and returning to the United States.

The panel achieves this remarkable feat by striking down two Justice Department regulations which (in tandem) require applicants for legalization under 8 U.S.C. § 1255a to obtain advance parole-the approval of the INS to return after a brief departure. Espinoza-Gutierrez v. Smith, 94 F.3d 1270, 1276-77 (9th Cir.1996). As a consequence of this ruling, applicants for legalization-unlike almost everyone else in the United States-are entitled to depart whenever they please; on return, they must be admitted even though they don’t have a valid visa or other advance authorization for entry. All they need do is show up at the border, prove they are applicants for legalization and tell their story. This puts legalization applieants-who entered the United States illegally to begin with-in a better position than United States citizens and aliens who entered this country lawfully.

Of course, it’s not easy to rip two Justice Department regulations from the CFR; to do so, the panel has to badly misread the law and do considerable damage to the proper relationship between the judicial and the political branches of government. The panel takes issue with the INS’s application of the Fleuti doctrine to legalization applicants seeking to reenter the United States. 2 It *552 finds fault with the regulations not because they substantively misapply Fleuti; clearly they do not, as the INS will grant advance parole to any alien whose departure meets Fleuti’s substantive standards (short stay, not intended to interrupt residency, etc.). The panel, rather, strikes down the regulations because they require legalization applicants to explain their reasons for leaving and obtain the INS’s approval before departing the United States. The flaws in this reasoning are numerous.

First, the panel strikes down the regulations, saying “we conclude that [8 U.S.C. § 1255a(a)(3)(B)-applying the Fleuti doctrine to legalization applicants] is not limited to those absences authorized in advance by the INS.” 94 F.3d at 1277 (emphasis added). But under Chevron, U.S.A. v. Natural Resources Defense Council, 467 U.S. 837 , 104 S.Ct. 2778 , 81 L.Ed.2d 694 (1984), the question is not what we conclude, but whether the construction adopted by the agency is reasonable. Id. at 842-43 , 104 S.Ct. at 2781-82 . In striking down the regulations the panel engages in de novo interpretation of the statue; it does not even pretend to give deference to the INS’s interpretation. This conflicts not only with Chevron, but with any number of our opinions holding that INS regulations must be upheld if they reflect a reasonable interpretation of the statute. E.g., Fisher v. INS, 79 F.3d 955, 961 (9th Cir.1996) (en banc); Ghaly v. INS, 58 F.3d 1425, 1429 (9th Cir.1995); Barrera-Echavarria v. Rison, 44 F.3d 1441, 1444 (9th Cir.) (en banc), cert. denied, — U.S. -, 116 S.Ct. 479 , 133 L.Ed.2d 407 (1995).

Second, the panel errs when it looks to section 1255a alone in reviewing the regulations. That section is not the only immigration statute the Attorney General is authorized to administer, nor is it the only immigration statute applicants for legalization must contend with. Quite aside from the specific authority of section 1255a, the Attorney General has plenary authority to enforce the immigration laws. One of the statutes on which the Attorney General may rely in promulgating regulations is 8 U.S.C. § 1181 , which requires aliens living in the United States to obtain documentary proof of their right to return. In adopting the regulations the panel strikes down, the Attorney General was authorized not only to draw upon her full authority, but also to consider the massive administrative burdens associated with verifying the admissibility of the hundreds of millions of people who cross our borders every year. See Fact Sheet: Cooperation with Mexico, Dept. St. Dispatch, May 22, 1995, at 425, 1995 WL 8643560 (331 million cross the United States-Mexico border alone).

The panel invalidates the regulations because they “require aliens to jump though several administrative hoops in order to receive advance parole.” 94 F.3d at 1277 . But everyone else who wants to leave the United States and come back must also jump through such hoops. I’m not entitled to leave for Australia and get back in by waving my naturalization certificate, just as natural-born citizens aren’t entitled to pull out a birth certificate and demand readmittance. No, we’re all required to “jump through ... administrative hoops” by applying for a passport in advance. Why? Because it would be an administrative nightmare if everyone entitled to enter the United States could insist on proving up their right to do so at the border. The Attorney General’s interest in the orderly administration of the immigration laws alone makes her advance parole requirement reasonable. See Stone v. INS, 514 U.S. 386 , -, 115 S.Ct. 1537, 1545 , 131 L.Ed.2d 465 (1995) (administrative efficiency is an important factor in interpreting the immigration laws); Heckler v. Campbell, 461 U.S. 458 , 461 n. 2, 103 S.Ct. 1952 , 1954 n. 2, 76 L.Ed.2d 66 (1983) (“need for efficiency is self-evident” concern when reviewing regulations that govern large numbers of claims).

In the case of legalization applicants, the Attorney General has even more at stake than the swift and orderly processing of individuals who present themselves at the border. Aliens seeking legalization must prove, except as permitted by Fleuti, that they have maintained continuous physical presence in the United States. See 8 U.S.C. § 1255a(a)(3)(A). The Attorney General *553 thus has a legitimate interest in documenting any departures to ensure that legalization applicants comply with the statutory requirements. It is far more difficult, of course, to figure out where an applicant has been and how long he’s been gone when the events must be reconstructed months or years later based on post-hoc evidence presented by the applicant. Moreover, the Attorney General may reasonably fear that an applicant who is not required to obtain advance authorization may leave for an extended stay, come back illicitly, and (if not stopped at the border) never advise the INS. The requirement of advance parole ensures that the INS is kept apprised of the alien’s departures and arrivals. It also requires contemporaneous documentation of a trip’s length and purpose, rather than forcing the INS to rely on whatever evidence the applicant comes up with if and when he’s caught.

I find remarkable the panel’s conclusion that an INS regulation serving so many legitimate purposes is not within the power of the Attorney General, who has been delegated plenary authority to regulate “the relationship between the United States and our alien visitors.” Reno v. Flores, 507 U.S. 292, 305 , 113 S.Ct. 1439, 1449 , 123 L.Ed.2d 1 (1993) (quoting Mathews v. Diaz, 426 U.S. 67, 81 , 96 S.Ct. 1883, 1892 , 48 L.Ed.2d 478 (1976)).

Third, the panel misreads Fleuti. According to the panel, “the Fleuti doctrine’s purpose [is] to circumvent entry procedures when aliens have not intended to disrupt their United States residency.” 94 F.3d at 1277 (emphasis added). This is a bizarre' reading of Fleuti, as the passage on which the panel relies demonstrates:

374 U.S. at 462, 83 S.Ct. at 1812 (quoted at 94 F.3d at 1277 ; emphasis added). This passage does not say-as the panel interprets it-that an alien whose departure is brief, casual and innocent is entitled to “circumvent” the entry procedures of the United States. For example, an alien can’t circumvent the requirement of border inspection by wading across the Rio Grande, on the theory that he’s never left the country and is therefore not required to make an official entry. What Fleuti says is that an alien who seeks to come in after a brief departure will not suffer “the consequences of an ‘entry.’ ” This means that, though the alien may have left and come back into the United Sates, the departure will be a legal nullity and not be deemed to interrupt the alien’s continuous residence.

Nowhere does the Supreme Court say that the alien is entitled to “circumvent” the ordinary procedural requirements of entering into the United States, such as inspection at a border crossing point and presentation of such documents as the Attorney General reasonably requires to establish compliance with Fleuti. The sentence immediately preceding the one quoted by the panel proves this:

Id. Had the Court meant to say that an alien who is entitled to depart may never be required to obtain advance documentation, this would have hardly be a factor that “might well cause” the doctrine not to apply; it would be a conclusive bar.

The panel raises the spectre of legalization applicants who depart the United States without advance parole because of extreme emergency or inadvertence, concluding it would be unfair to exclude these aliens because they “did not intend to disrupt meaningfully their United States residency.” 94 F.3d at 1277 . I might have no quarrel with an opinion holding that it is arbitrary and capricious to apply the regulations under those unusual circumstances. It may well be, for example, that excluding an alien because his train happened to pass through Canada would violate Fleuti. See DiPasquale v. Karnuth, 158 F.2d 878 (2d Cir.1947). That is not this case. Espinoza faced no *554 emergency; he did not wander across the border inadvertently. So far as the record shows, he had the time and wherewithal to seek advance parole. I can see no justification for striking down the regulations in their entirety to benefit someone in Espinoza’s position, someone who could well have complied. To strike down both regulations because-in certain rare and difficult cases-they are capable of harsh and capricious application amounts to vast judicial overreaching, especially where we are not faced with a case of emergency. The far more prudent eourse- and the one required by Chevron-is to uphold the regulations as to Espinoza, and reserve for another day the case where the regulations impose a harsh or unconscionable result.

Finally, the reason the panel gives for striking down the regulations-that requiring legalization applicants to obtain advance parole as a condition for reentry is “a far cry from a liberal and generous application of [section 1255a] as intended by Congress,” 94 F.3d at 1277 -is patently inconsistent with another portion of the opinion, where the panel admits that the statute does not require the INS to readmit any legalization applicants at the border if they leave the country. Id. at 1275-76 . It’s absurd to argue that the INS may, consistent with section 1255a, preclude aliens from reentering after even the briefest departure, yet hold that the far more generous policy of allowing advance parole is an insufficiently liberal and generous application of the statute. These two portions of the opinion are logically inconsistent and cannot be reconciled.

The opinion creates a conflict with numerous Ninth Circuit cases holding that INS. regulations are entitled to Chevron deference. See pp. 551-52 supra. A direct conflict with another circuit doesn’t yet exist, but one may be on the horizon. 3 Most importantly, however, “[t]his case presents a question of exceptional importance regarding the Attorney General’s authority to control the border and to regulate the travel of illegal aliens who have applied for legalization____” Petition for Rehearing at 1; Fed.RApp.P. 35(a)(2). The opinion is an obvious misapplication of Chevron, and an egregious intrusion upon the Attorney General’s authority to administer the immigration laws. Because we should have set our own house in order, I dissent.

. There is one exception expressly authorized by Congress. Seasonal agricultural workers who meet the requirements detailed in 8 U.S.C. § 1160 may apply for temporary resident status, and while their applications are pending, may not be “excluded or deported.” Id. § 1160(d).

. The Fleuti doctrine holds that aliens lawfully living in the United States are "not subject ... to the consequences of an 'entry' into the country” upon their return from an "innocent, casual, and brief” departure. Rosenberg v. Fleuti, 374 U.S. 449, 462 , 83 S.Ct. 1804, 1812 , 10 L.Ed.2d 1000 (1963). The doctrine originally applied only to lawful permanent resident aliens, but Congress has extended it to cover other classes of aliens as well. See 8 U.S.C. §§ 1254 (b)(2) (applicants for suspension of deportation); 1254a(c)(4) (foreign nationals seeking temporary resident status). Section 1255a(a)(3)(B), the statute at issue here, creates an exception to the general rule that legalization applicants must remain in the United *552 States continuously, excusing those absences that are "brief, casual, and innocent.”

. Fernandes v. McElroy, 920 F.Supp. 428 (S.D.N.Y.1996), in which a district court reviewing the denial of an alien’s legalization application also invalidated the INS’s advance parole regulations, is currently on appeal before the Second Circuit.